diff options
Diffstat (limited to 'paper/sections/model.tex')
| -rw-r--r-- | paper/sections/model.tex | 19 |
1 files changed, 8 insertions, 11 deletions
diff --git a/paper/sections/model.tex b/paper/sections/model.tex index d8706bc..01f816b 100644 --- a/paper/sections/model.tex +++ b/paper/sections/model.tex @@ -18,9 +18,7 @@ state space $\{0, 1, \dots, K-1\}^V$ with the following properties: \end{enumerate} In other words, a cascade model describes a diffusion process where a set of -contagious nodes ``influence'' other nodes in the graph to become in turn -contagious. An \emph{influence cascade} is a realisation of this random -process: the successive states of the nodes in graph ${\cal G}$. Note that both +contagious nodes ``influence'' other nodes in the graph to become contagious. An \emph{influence cascade} is a realisation of this random process, \emph{i.e.} the successive states of the nodes in graph ${\cal G}$. Note that both the ``single source'' assumption made in \cite{Daneshmand:2014} and \cite{Abrahao:13} as well as the ``uniformly chosen source set'' assumption made in \cite{Netrapalli:2012} verify condition 3. @@ -33,7 +31,7 @@ a more general class of transition probabilities while staying in the discrete-time setting. We observe that despite their obvious differences, both the independent cascade and the voter models make the graph inference problem similar to the standard generalized linear model inference problem. In fact, we -define a class of diffusion processes for which this true: the +define a class of diffusion processes for which this is true: the \emph{Generalized Linear Cascade Models}. The linear threshold model is a special case and is discussed in Section~\ref{sec:linear_threshold}. @@ -101,7 +99,7 @@ In the independent cascade model, nodes can be either susceptible, contagious or immune. At $t=0$, all source nodes are ``contagious'' and all remaining nodes are ``susceptible''. At each time step $t$, for each edge $(i,j)$ where $j$ is susceptible and $i$ is contagious, $i$ attempts to infect $j$ with -probability $p_{i,j}\in[0,1]$, the infection attempts are mutually independent. +probability $p_{i,j}\in(0,1]$; the infection attempts are mutually independent. If $i$ succeeds, $j$ will become contagious at time step $t+1$. Regardless of $i$'s success, node $i$ will be immune at time $t+1$. In other words, nodes stay contagious for only one time step. The cascade process terminates when no @@ -126,8 +124,7 @@ with inverse link function $f : z \mapsto 1 - e^z$. \subsubsection{The Linear Voter Model} -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 +In the Linear Voter Model, nodes can be either \emph{red} or \emph{blue}. 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$ and we assume that $\Theta_{i,i}$ is always non-zero, meaning that all nodes have self-loops. @@ -188,8 +185,8 @@ problem: \hat{\Theta} \in \argmax_{\Theta} \frac{1}{n} \mathcal{L}(\Theta\,|\,x^1,\ldots,x^n) - \lambda\|\Theta\|_1 \end{displaymath} -where $\lambda$ is the regularization factor which helps at preventing -overfitting as well as controlling for the sparsity of the solution. +where $\lambda$ is the regularization factor which helps preventing +overfitting and controls the sparsity of the solution. The generalized linear cascade model is decomposable in the following sense: given Definition~\ref{def:glcm}, the log-likelihood can be written as the sum @@ -209,8 +206,8 @@ where we denote by ${\cal T}_i$ the time steps at which node $i$ is susceptible 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 +until node $i$ becomes contagious, after which its behavior is deterministic. +Contrary to prior work, our results depend on 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 |