diff options
Diffstat (limited to 'paper')
| -rw-r--r-- | paper/sections/model.tex | 99 |
1 files changed, 71 insertions, 28 deletions
diff --git a/paper/sections/model.tex b/paper/sections/model.tex index bbfd96c..dbcbd8d 100644 --- a/paper/sections/model.tex +++ b/paper/sections/model.tex @@ -1,27 +1,69 @@ -We consider a graph ${\cal G}= (V, E, \Theta)$, where $\Theta$ is a $|V|\times |V|$ matrix of parameters describing the edge weights of $\mathcal{G}$. Let $m\defeq |V|$. For each node $j$, let $\Theta_{j}$ be the $j^{th}$ column vector of $\Theta$. Intuitively, $\Theta_{i,j}$ captures the ``influence'' of node $i$ on node $j$. A \emph{Cascade model} is a Markov process over a finite state space $\{0, 1, \dots, K-1\}^V$ with the following properties: +We consider a graph ${\cal G}= (V, E, \Theta)$, where $\Theta$ is a $|V|\times +|V|$ matrix of parameters describing the edge weights of $\mathcal{G}$. +Intuitively, $\Theta_{i,j}$ captures the ``influence'' of node $i$ on node $j$. +Let $m\defeq |V|$. For each node $j$, let $\theta_{j}$ be the $j^{th}$ column +vector of $\Theta$. A \emph{Cascade model} is a Markov process over a finite +state space $\{0, 1, \dots, K-1\}^V$ with the following properties: \begin{enumerate} -\item Conditioned on the previous time step, the transition probabilities for each node $i \in V$ are mutually independent. -\item Of the $K$ possible states, there exists a \emph{contagious state} such that all transition probabilities of the Markov process are either constant or can be expressed as a function of the graph parameters $\Theta$ and the set of ``contagious nodes'' at the previous time step. -\item The initial probability over $\{0, 1, \dots, K-1\}^V$ of the Cascade Model is such that all nodes can eventually reach a \emph{contagious state} with non-zero probability. The ``contagious'' nodes at $t=0$ are called \emph{source nodes}. + \item Conditioned on the previous time step, the transition events between + two states in $\{0,1,\dots, K-1\}$ for each $i \in V$ are mutually + independent. +\item Of the $K$ possible states, there exists a \emph{contagious state} such + that all transition probabilities of the Markov process are either constant + or can be expressed as a function of the graph parameters $\Theta$ and the + set of ``contagious nodes'' at the previous time step. +\item The initial probability over $\{0, 1, \dots, K-1\}^V$ of the Cascade + Model is such that all nodes can eventually reach a \emph{contagious state} + with non-zero probability. The ``contagious'' nodes at $t=0$ are called + \emph{source nodes}. \end{enumerate} -In other words, a cascade model describes a diffusion process, whereby a set of contagious nodes ``influence'' other nodes in the graph to adopt or not their behavior. An \emph{influence cascade} is a realisation of this random process: 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. +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 +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. -In the context of Graph Inference, \cite{Netrapalli:2012} focuses specifically on the well-known discrete-time independent cascade model recalled below, which \cite{Abrahao:13} and \cite{Daneshmand:2014} generalize to continuous time. Whilst we restrict ourselves to discrete-time processes, we consider both the independent cascade model and the linear voter model. Despite their obvious differences, both models make the graph inference problem very similar to the standard generalized linear model estimation problem. In fact, we can define a class of diffusion processes which for which this true: the \emph{Generalized Linear Cascade Models}. The linear threshold model is a special case and is discussed in Section~\ref{sec:linear_threshold}. +In the context of Graph Inference, \cite{Netrapalli:2012} focuses specifically +on the well-known discrete-time independent cascade model recalled below, which +\cite{Abrahao:13} and \cite{Daneshmand:2014} generalize to continuous time. We +extend the independent cascade model in a different direction by considering +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 +\emph{Generalized Linear Cascade Models}. The linear threshold model is +a special case and is discussed in Section~\ref{sec:linear_threshold}. \subsection{Generalized Linear Cascade Models} \label{sec:GLC} -Let \emph{susceptible} characterize any state which can become contagious at the next time step with a non-zero probability. We draw inspiration from generalized linear models to introduce Generalized Linear Cascades: +Let \emph{susceptible} denote any state which can become contagious at +the next time step with a non-zero probability. We draw inspiration from +generalized linear models to introduce Generalized Linear Cascades: \begin{definition} \label{def:glcm} -Let $X^t$ be the indicator variable of ``contagious nodes'' at time step $t$. 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$ conditionally on $X^t$ is a Bernoulli of parameter $f_s(\Theta_j \cdot X^t)$: -$$\mathbb{P}(X^{t+1}_j = 1|X^t \text{and } e^t_j = s) = f_s(\Theta_j \cdot X^t)$$ -where $e^t_j$ is the state of node $j$ at time step $t$ and $f_s : \mathbb{R} \rightarrow [0,1]$ +Let $X^t$ be the indicator variable of ``contagious nodes'' at time step $t$. +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} + \mathbb{P}(X^{t+1}_j = 1|X^t) + = f(\theta_j \cdot X^t) +\end{displaymath} +where $f: \reals \rightarrow [0,1]$ \end{definition} -In other words, each generalized linear cascade provides a series for each node $j \in V$ a series of measurements $(X^t, X^t_j)_{t \in {\cal T_j}}$ issued from a generalized linear model. Note also that $\E[X^{t+1}_i\,|\,X^t] = f(\inprod{\theta_i}{X^t})$. As such, $f$ can be interpreted as the inverse link function of our generalized linear cascade model. +In other words, each generalized linear cascade provides, for each node $j \in +V$ a series of measurements $(X^t, X^t_j)_{t \in {\cal T}_j}}$ sampled from +a generalized linear model. Note also that $\E[X^{t+1}_i\,|\,X^t] += f(\inprod{\theta_i}{X^t})$. As such, $f$ can be interpreted as the inverse +link function of our generalized linear cascade model. % Denoting by $X^t$ the state of the cascade at time step $t$, we interpret % $X^t_j = 1$ for node $j\in V$ as ``node $j$ is contagious'', \emph{i.e}, ``$j$ @@ -55,14 +97,15 @@ In other words, each generalized linear cascade provides a series for each node \subsubsection{Independent Cascade Model} -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 independent of each other. 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 contagious nodes remain. +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. +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 +contagious nodes remain. If we denote by $X^t$ the indicator variable of the set of contagious nodes at time step $t$, then if $j$ is susceptible at time step $t+1$, we have: @@ -79,14 +122,16 @@ Defining $\Theta_{i,j} \defeq \log(1-p_{i,j})$, this can be rewritten as: \end{equation} Therefore, the independent cascade model is a Generalized Linear Cascade model -with canonical link function $f : z \mapsto 1 - e^z$. +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 symetric, but without loss of generality, we can suppose that the \emph{blue} nodes are contagious and the \emph{red} nodes are susceptible. The parameters of the graph are normalized such that $\forall i, +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 -cascades stops at a fixed horizon time T or if all nodes are of the same color. +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: \begin{equation} @@ -95,7 +140,7 @@ step $t$, then we have: \end{equation} Therefore, the independent cascade model is a Generalized Linear Cascade model -with canonical link function $f: z \mapsto z$. +with inverse link function $f: z \mapsto z$. % \subsection{The Linear Threshold Model} @@ -124,16 +169,14 @@ with canonical link function $f: z \mapsto z$. \subsection{Maximum Likelihood Estimation} \label{sec:mle} -Recovering the model parameter $\Theta$ from observed influence cascades is the +Inferring the model parameter $\Theta$ from observed influence cascades is the central question of the present work. Recovering the edges in $E$ from observed influence cascades is a well-identified problem known as the \emph{Graph Inference} problem. However, recovering the influence parameters is no less important and has been seemingly overlooked so far. In this work we focus on recovering $\Theta$, noting that the set of edges $E$ can then be recovered -through the following equivalence: -\begin{displaymath} - (i,j)\in E\Leftrightarrow \Theta_{i,j} \neq 0 -\end{displaymath} +through the following equivalence: $(i,j)\in E\Leftrightarrow \Theta_{i,j} +\neq 0$ Given observations $(x^1,\ldots,x^n)$ of a cascade model, we can recover $\Theta$ via Maximum Likelihood Estimation (MLE). Denoting by $\mathcal{L}$ the |