diff options
Diffstat (limited to 'notes/formalisation.tex')
| -rw-r--r-- | notes/formalisation.tex | 25 |
1 files changed, 20 insertions, 5 deletions
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} |