aboutsummaryrefslogtreecommitdiffstats
path: root/paper/sections/model.tex
diff options
context:
space:
mode:
Diffstat (limited to 'paper/sections/model.tex')
-rw-r--r--paper/sections/model.tex23
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...