diff options
Diffstat (limited to 'theory')
| -rw-r--r-- | theory/main.tex | 142 |
1 files changed, 138 insertions, 4 deletions
diff --git a/theory/main.tex b/theory/main.tex index d293b6f..505f722 100644 --- a/theory/main.tex +++ b/theory/main.tex @@ -64,6 +64,7 @@ the following ways: \end{itemize} \subsection{Pairwise Propagation} +\label{sec:edge} For a pair $(u,v)$ of nodes, we model the propagation of the cascade from $u$ to $v$ as the sequence of the following two probabilistic events: @@ -101,26 +102,159 @@ from $u$ to $v$ as the sequence of the following two probabilistic events: In our data, the infection times are only observed with a temporal resolution of one day. As a consequence, for two nodes $u$ and $v$ - whose \empb{observed} infection times are respectively $t_u$ and $t_v$ + whose \emph{observed} infection times are respectively $t_u$ and $t_v$ (days), the \emph{real} propagation time could be anything in the interval $(t_v-t_u-1, t_v-t_u]$. Hence, the probability of observing a propagation time $\Delta_{u,v} = t_v - t_u$ is given by: \begin{equation}\label{eq:temporal} - p_{u,v}^t \eqdef \int_{\Delta_{u,v}-1}^{\Delta_{u,v}} f(t)dt + p_{u,v}^t(\Delta_{u,v}) \eqdef \int_{\Delta_{u,v}-1}^{\Delta_{u,v}} f(t)dt \end{equation} +\end{enumerate} \paragraph{Successful propagation.} For two nodes $u$ and $v$ with observed infection times $t_u$ and $t_v$, the probability $p_{u,v}$ that $u$ infected $v$ is obtained by multiplying the structural and temporal probabilities given by \eqref{eq:structural} and \eqref{eq:temporal}: \begin{displaymath} - p_{u,v} \eqdef p_{u,v}^s\cdot p_{u,v}^t + p_{u,v}(t_u, t_v) \eqdef p_{u,v}^s\cdot p_{u,v}^t(\Delta_{u,v}) \end{displaymath} -\subsection{Spawning of New Cascades} +\subsection{Failed Propagations and Spawning of New Cascades} +\label{sec:roots} + +\paragraph{Failed propagation.} +When an edge fails to propagate the violence cascade, it could be either +because the structural propagation did not occur, or because the structural +propagation occurred, but the temporal propagation didn't occur in time. + +For an edge $(u,v)$ with infection times $t_u$ and $t_v$, it follows directly +from Section~\ref{sec:edge} that structural propagation does not occur with +probability $1-p_{u,v}^s$. + +If structural propagation occurs, but temporal propagation does not occur in +time, it means that node $v$ was infected at time $t_v$ (through other means) +\emph{before} $u$ succeeds in infecting $v$. That is, the propagation time was +larger than $\Delta_{u,v}$. This occurs with probability: +\begin{displaymath} + \int_{\Delta_{u,v}}^{+\infty} f(t)dt = 1-F(\Delta_{u,v}) +\end{displaymath} + +Overall, the probability of a failed propagation over an edge $(u,v)$ is given +by: +\begin{displaymath} + \tilde{p}_{u,v}(t_u, t_v) + \eqdef 1 - p_{u,v}^s + p_{u,v}^s\left(1-F(\Delta_{u,v})\right) + = 1 - p_{u,v}^s F(\Delta_{u,v}) +\end{displaymath} + +\paragraph{}For an edge $(u,v)$ where $u$ is a victim node and $v$ is a not +a victim, the situation is similar: either the structural propagation failed, +or it succeeded but the temporal propagation did not occur in time. In the +latter case, since we did not observe an infection at all for $v$, this means +that the propagation time between $u$ and $v$ was such that the infection time +of $v$ would have fallen after the end of the study period. Denoting by $T$ the +observation horizon (the end of the study period), the probability of a failed +propagation for an edge $(u,v)$ where $v$ is not a victim is: +\begin{displaymath} + \tilde{p}_{u,v}(t_u, T) \eqdef 1-p_{u,v}^s F(T-t_u) +\end{displaymath} + +\paragraph{Spawning of New Cascades.} + +Our probabilistic model considers another cause of infection for victim nodes: +beyond pairwise propagation of the violence cascade, nodes can also +spontaneously become infected and spawn a new violence cascade. We simply model +this by a Bernouilli variable of parameter $\beta$: for any node, the +probability that it becomes infected spontaneously is $\beta$. + +\subsection{The Directed Acyclic Vector of Infection} +\label{sec:dag} + +It follows from Sections~\ref{sec:edge} and \ref{sec:roots} that \emph{(1)} no +infection can occur between two non victim nodes, \emph{(2)} no infection can +occur along an edge $(u,v)$ where $t_u > t_v$. + +This suggests to orient and trim the co-offending network $G$ to construct the +following directed graph $D$ by applying the following rules: +\begin{enumerate} + \item remove edges between non-victim nodes. + \item orient edges from victim nodes to non-victim nodes. + \item for any edge $(u,v)$ between two victims, orient it in the direction + from smallest infection time to largest infection time. +\end{enumerate} + +The resulting graph $D$ only contains edges along with the propagation of +violence can possibly occur. Furthermore the edges are oriented in the +direction of propagation. + +It has been observed in (CITE) that $D$ is acyclic. For completeness we +reproduce their proof here and adapt it to account for non-victim nodes (which +do not exist in the original paper). + +\begin{theorem} +The graph $D$ obtained from $G$ by applying rules 1. to 3. is acyclic. +\end{theorem} + +\begin{proof} + Assume by contradiction that $D$ contains a cycle $(u_1,\ldots, u_n)$ where + $(u_1, u_2),\dots,(u_{n-1}, u_n), (u_n, u_1)$ are edges of $D$. Because of + rule 1., all nodes $u_1,\dots, u_n$ are victim nodes. + + Applying rule 3. to all edges in the cycle implies that + $t_1<t_2<\dots<t_n<t_1$. The two extremal terms of this chain of + inequalities implie $t_1<t_1$ which is a contradiction. +\end{proof} \subsection{Cascade Model} +Using Sections~\ref{sec:edge} to \ref{sec:dag}, we can now fully specify our +cascade model. + +The violence propagation proceeds as follows: every time a node becomes +infected, it attempts to infect all its neighbors which are not infected yet +according to the pairwise model of Section~\ref{sec:edge}. In other words, at +a given time, a node is subjected to the ongoing infection attempts of all its +neighbors which have been infected in the past. Because of the temporal +component of the pairwise propagation probabilities, these attempts will +succeed at different times. The infection is attributed to the first neighbor +who succeeds.Furthermore, all the infection attempts are independent from each +other. + +\paragraph{Example.} Let us consider a node $v$ with $n$ neighbors $u_1,\dots, +u_n$. For simplicity, let us assume that the structural propagation +probabilities are the same and equal to one for all edges $(u_i, v)$. We also +assume that all neighbors of $v$ were infected at time $0$ and we use the +exponential temporal model with parameter $\alpha$. Then, the probability that +$v$ is infected at time larger than $t$ is given by: +\begin{displaymath} + p_v(t) \eqdef \P\left[\min_{1\leq i\leq n} Z_i \geq t\right] + = e^{-n\alpha t} +\end{displaymath} +where $Z_i$ is an exponential variable of parameter $\alpha$ and where we used +that the law of the minimum of exponential variables is also exponential with +parameter equal to the sum of the individual variables' parameters. + +This example shows that the larger the neighborhood the more likely it is that +a node will be infected quickly. The parameter $\alpha n$ of the resulting +exponential variable captures the aggregated infection potential of the +neighborhood. + +\paragraph{} Since the infection of a node $v$ is always attributed to the +first neighbor which succeeds in infecting it, a victim node +can have at either one parent (when it is infected by it) or no parent (when it +spawns a cascade spontaneously). Because the graph $D$ along which the cascades +of violence occur is acyclic, it follows that the violence propagates along $D$ +by forming trees. + +Formally, if we denote by $(V, E)$ the vertices and edges of $D$, and we write +$V = R\cup T$ where $R$ are the victim nodes and $T$ the non-victim nodes +($R\cap T=\emptyset$), then \emph{the violence cascades form a random forest +spanning $R$ in $D$}. + +Given a random forest $(T_1,\dots T_r)$ spanning $R$, where $T_i, 1\leq i\leq +n$ are trees, we can compute the probability of this forest occurring according +to the model + \section{Maximum Likelihood Inference} \subsection{Finding the Cascades} |