voter model

2 files changed, 20 insertions, 5 deletions

diff --git a/notes/formalisation.pdf b/notes/formalisation.pdf
index ed7aa1e..9383d54 100644
--- a/notes/formalisation.pdf
+++ b/notes/formalisation.pdf
diff --git a/notes/formalisation.tex b/notes/formalisation.tex
index f80885e..acc58d2 100644
--- a/notes/formalisation.tex
+++ b/notes/formalisation.tex
@@ -1,5 +1,6 @@
 \documentclass[10pt]{article}
 \usepackage[utf8x]{inputenc}
+\usepackage{fullpage}
 \usepackage{amsmath, amssymb, bbm, amsthm}
 \usepackage[pagebackref=true,breaklinks=true,colorlinks=true,backref=false]{hyperref}
 \usepackage[capitalize, noabbrev]{cleveref}
@@ -102,7 +103,8 @@ In the voter model, there are two types of nodes, {\it red} and {\it blue}. We f
 
 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:
+\paragraph{Notation}
+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$. In other words, $M^t_k$ is a vector in $\mathbb{R}^n$ such that:
 
 \[ (M^t_k)_j = \left\{ 
   \begin{array}{l l}
@@ -110,17 +112,30 @@ Denote by $(M^t_k)_{1 \leq k \leq m; 1 \leq t \leq T}$ the set of blue nodes in
     0 & \quad \text{otherwise}
   \end{array} \right.\]
 
-Consider a node $i$, and let $\theta_i$ be a vector in $\mathbb{R}^n$ such that:
+Consider a node $i$, and let $\theta_i$ be the vector representing the neighbors of $i$ in the graph {\cal G}. In other words, $\theta_i$ is 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$}\\
+    1/deg(i) & \quad \text{if $j$ is a parent of $i$ in {\cal G}}\\
     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 
+Let $b^t_k$ be the vector representing the probability that in cascade $k$ at time step $t$ node $i$ stays or becomes $blue$.
+
+\[ b^t_k = \left\{ 
+  \begin{array}{l l}
+    (\text{Number of $blue$ neighbors in $(k, t-1$})/deg(i) & \quad \text{if $t\neq 0$}\\
+    1/p_{\text{init}} & \quad \text{otherwise}
+  \end{array} \right.\]
+
+Our objective is to find the neighbors of $i$ in {\cal G} from $(M^t_k)$ i.e recover the vector $\theta_i$. Notice that for each $(k,t)$, we have:
+
+$$\forall t< T-1, k, \ M^t_k \cdot \theta_i = b^{t+1}_k$$
+
+We can concatenate each equality in matrix form $M$, such that the rows of $M$ are the observed $blue$ nodes $M^t_k$ and the entries of $\vec b$ are the corresponding probabilities:
+
+$$M \cdot \theta = \vec b$$
 
-$$\frac{\text{Number of blue neighbors}}{deg(i)} = M^t_k \cdot \theta_i$$
 
 
 \section{Independent Cascade Model}