diff options
| -rw-r--r-- | notes/formalisation.pdf | bin | 200068 -> 202829 bytes | |||
| -rw-r--r-- | notes/formalisation.tex | 23 |
2 files changed, 22 insertions, 1 deletions
diff --git a/notes/formalisation.pdf b/notes/formalisation.pdf Binary files differindex 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} |