From e8db4c8e2da97497e3ffbce3394444ccdea6059f Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Sun, 25 Jan 2015 16:17:05 -0500
Subject: More model

---
 paper/sections/model.tex | 36 ++++++++++++++++++++++++++++++++++--
 1 file changed, 34 insertions(+), 2 deletions(-)

(limited to 'paper/sections/model.tex')

diff --git a/paper/sections/model.tex b/paper/sections/model.tex
index 11de7d2..5097c63 100644
--- a/paper/sections/model.tex
+++ b/paper/sections/model.tex
@@ -42,11 +42,43 @@ The goal of this paper is to characterize $\hat{\Theta}$ in terms of:
 
 We now turn to two widely used influence cascade models, the Independent
 Cascade Model (IC) and the Linear Threshold Model (LT) and specify the MLE
-problem \eqref{eq:mle} for these models
+problem \eqref{eq:mle} for these models.
+
+\subsection{Independent Cascade Model}
+
+In the independent cascade model, nodes can be either uninfected, active or
+infected. All nodes start either as uninfected or active. At each time step
+$t$, for each edge $(i,j)$ where $j$ is uninfected and $i$ is active, $j$
+attempts to infect $j$ with probability $p_{i,j}$. If $i$ succeeds, $j$ will
+become active at time step $t+1$. Regardless of $i$'s success, node $i$ will be
+infected at time $t+1$: nodes stay active for only one time step. The cascade
+continues until no active nodes remain.
+
+If we denote by $X^t$ the indicator variable of the set of active nodes at time
+step $t-1$, then if $j$ is uninfected at time step $t-1$, we have:
+\begin{displaymath}
+    \P\big[X^{t+1}_j = 1\,|\, X^{t}\big]
+    = 1 - \prod_{i = 1}^m (1 - p_{i,j})^{X^t_i}
+    = 1 - e^{\inprod{\theta_j}{X^t}}
+\end{displaymath}
+where we defined $\Theta_{i,j} \defeq \log(1-p_{i,j})$.
 
 \subsection{Linear Threshold Model}
 
-\subsection{Independent Cascade Model}
+In the Linear Threshold Model, each node $j\in V$ has a threshold $t_j$ drawn
+uniformly from the interval $[0,1]$. We assume that the weights given by
+$\Theta$ are such that for each node $j\in V$, $\sum_{i=1}^m \Theta_{i,j} \leq
+1$.
+
+Nodes can be either infected or uninfected. At each time step, each uninfected
+node $j$ becomes infected if the sum of the weights $\Theta_{i,j}$ where $i$ is
+an infected parent of $j$ is larger than $j$'s threshold $t_j$. Denoting by
+$X^t$ the indicator variable of the set of infected nodes at time step $t-1$,
+if $j\in V$ is uninfected at time step $t-1$, then:
+\begin{displaymath}
+    \P\big[X^{t+1}_j = 1\,|\, X^{t}\big] = \sum_{i=1}^m \Theta_{i,j}X^t_i
+    = \inprod{\theta_j}{X^t}
+\end{displaymath}
 
 \subsection{Unification}
 
-- 
cgit v1.2.3-70-g09d2

