voter model

2 files changed, 22 insertions, 1 deletions

diff --git a/notes/formalisation.pdf b/notes/formalisation.pdf
index 7692c7f..ed7aa1e 100644
--- a/notes/formalisation.pdf
+++ b/notes/formalisation.pdf
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}