diff options
Diffstat (limited to 'paper/sections/model.tex')
| -rw-r--r-- | paper/sections/model.tex | 23 |
1 files changed, 16 insertions, 7 deletions
diff --git a/paper/sections/model.tex b/paper/sections/model.tex index dbcbd8d..cf69960 100644 --- a/paper/sections/model.tex +++ b/paper/sections/model.tex @@ -52,10 +52,11 @@ A \emph{generalized linear cascade model} is a cascade model such that for each susceptible node $j$ in state $s$ at time step $t$, the probability of $j$ becoming ``contagious'' at time step $t+1$ conditioned on $X^t$ is a Bernoulli variable of parameter $f(\theta_j \cdot X^t)$: -\begin{displaymath} +\begin{equation} + \label{eq:glm} \mathbb{P}(X^{t+1}_j = 1|X^t) = f(\theta_j \cdot X^t) -\end{displaymath} +\end{equation} where $f: \reals \rightarrow [0,1]$ \end{definition} @@ -128,9 +129,11 @@ with inverse link function $f : z \mapsto 1 - e^z$. In the Linear Voter Model, nodes can be either \emph{red} or \emph{blue}. Both states are symmetric, but without loss of generality, we can suppose that the -\emph{blue} nodes are contagious. The parameters of the graph are normalized such that $\forall i, -\ \sum_j \Theta_{i,j} = 1$. Each round, every node $j$ independently chooses -one of its neighbors with probability $\Theta_{ij}$ and adopts their color. The +\emph{blue} nodes are contagious. The parameters of the graph are normalized +such that $\forall i, \ \sum_j \Theta_{i,j} = 1$ and we assume that +$\Theta_{i,i}$ is always non-zero, meaning that all nodes have self-loops. +Each round, every node $j$ independently chooses +one of its neighbors with probability $\Theta_{i,j}$ and adopts their color. The cascades stops at a fixed horizon time $T$ or if all nodes are of the same color. If we denote by $X^t$ the indicator variable of the set of blue nodes at time step $t$, then we have: @@ -139,7 +142,7 @@ step $t$, then we have: \tag{V} \end{equation} -Therefore, the independent cascade model is a Generalized Linear Cascade model +Thus, the independent cascade model is a Generalized Linear Cascade model with inverse link function $f: z \mapsto z$. % \subsection{The Linear Threshold Model} @@ -204,6 +207,13 @@ where we denote by ${\cal T}_i$ the time steps at which node $i$ is susceptible + (1 - x_i^{t+1})\log\big(1-f(\inprod{\theta_i}{x^t})\big) \end{multline*} +In the case of the voter model, the measurements include all time steps until +we reach the time horizon $T$ or the graph coalesces to a single state. In the +case of the independent cascade model, the measurements include all time steps +until node $i$ becomes contagious after which its behavior is deterministic. +Contrary to prior work, we express our results in terms of the number of +measurements and not the number of cascades. + A sufficient condition for program~\eqref{eq:pre-mle} to be a convex program is that $\mathcal{L}_i$ is a concave function. This will be the case if, for example, $f$ and $(1-f)$ are both log-concave functions. Remember that @@ -211,4 +221,3 @@ a twice-differentiable function $f$ is log concave iff. $f''f \leq f'^2$. It is easy to verify this property for $f$ and $(1-f)$ in the Independent Cascade Model and Voter Model. -Note that in the case of the voter model, TODO horizon time. In the case of the independent cascade model... |
