From 6be224d33a6f656f7b2d9ccca759b9a36336b1db Mon Sep 17 00:00:00 2001 From: jeanpouget-abadie Date: Sun, 23 Nov 2014 13:09:31 -0500 Subject: voter model --- notes/formalisation.pdf | Bin 200068 -> 202829 bytes notes/formalisation.tex | 23 ++++++++++++++++++++++- 2 files changed, 22 insertions(+), 1 deletion(-) (limited to 'notes') diff --git a/notes/formalisation.pdf b/notes/formalisation.pdf index 7692c7f..ed7aa1e 100644 Binary files a/notes/formalisation.pdf and b/notes/formalisation.pdf differ diff --git a/notes/formalisation.tex b/notes/formalisation.tex index 54f7efd..f80885e 100644 --- a/notes/formalisation.tex +++ b/notes/formalisation.tex @@ -97,9 +97,30 @@ For small $\delta_T$, the above equation defines a `loose' orthonormality proper \section{Warm up: the voter model} -In the voter model, there are two types of nodes, {\it red} and {\it blue}. At every turn, each node $u$ chooses one of its neighbors uniformly (with probability $\frac{1}{deg(u)}$) and adopts the color of that neighbor. In most cases, we consider that the graphs includes self-loops, meaning the node has the option to keep his color for the next round. We fix a horizon $T$, and a set of {\it blue} nodes, and we observe the evolution of set of $red$ nodes. +In the voter model, there are two types of nodes, {\it red} and {\it blue}. We fix a horizon $T$. At $t=0$, we decide on a set of {\it blue} nodes, called the seeding set. At each time step $t$, each node $u$ chooses one of its neighbors uniformly, with probability $1/deg(u)$, and adopts the color of that neighbor. A cascade in the voter model is the evolution of which nodes $blue$ nodes for each time step $ 0 \leq t \leq T$. +For simplicity, we suppose that every node has a probability $1/p_\text{init}$ of being a part of the seeding set of a cascade. The following analysis can easily be adapted to a non-uniform probability vector. We also suppose that the graphs includes self-loops, meaning the node has the option to keep his color for the next round. This is a common assumption which does not change any of the following results. + +Denote by $(M^t_k)_{1 \leq k \leq m; 1 \leq t \leq T}$ the set of blue nodes in cascade $k$ at time step $t$: $M^t_k$ is a vector in $\mathbb{R}^n$ such that: + +\[ (M^t_k)_j = \left\{ + \begin{array}{l l} + 1 & \quad \text{if $j$ is $blue$ in cascade $k$ at time step $t$}\\ + 0 & \quad \text{otherwise} + \end{array} \right.\] + +Consider a node $i$, and let $\theta_i$ be a vector in $\mathbb{R}^n$ such that: + +\[ \theta_{ij} = \left\{ + \begin{array}{l l} + 1/deg(i) & \quad \text{if $j$ is a parent of $i$}\\ + 0 & \quad \text{otherwise} + \end{array} \right.\] + +Our objective is to find the parents of $i$ from $(M^t_k)$ i.e recover the vector $\theta_i$. Notice that for a given cascade $k$, regardless of $i$'s color at time step $t$, the probability that it stays or becomes $blue$ at time step $t+1$ is + +$$\frac{\text{Number of blue neighbors}}{deg(i)} = M^t_k \cdot \theta_i$$ \section{Independent Cascade Model} -- cgit v1.2.3-70-g09d2