path: root/supplements/main.tex

\documentclass{article}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath}
\usepackage{algorithm}% http://ctan.org/pkg/algorithms
\usepackage{algpseudocode}% http://ctan.org/pkg/algorithmicx
\usepackage{graphicx}
\usepackage{microtype}
\usepackage{verbatim}

\DeclareMathOperator*{\argmax}{argmax}
\providecommand{\e}[1]{\ensuremath{\times 10^{#1}}}
\newcommand{\given}{\,|\,}

\title{Hawkes contagion model}
\author{Ben Green \and Thibaut Horel \and Andrew Papachristos}
\date{September 2015}

\begin{document}

\maketitle

\section{Contagion Model}

We model the contagion of violence using a multi-dimensional Hawkes process
over the co-offending network. Section~\ref{sec:background} briefly presents
the general definition of Hawkes Processes which is then instantiated and
adapted to the contagion of gun violence in Section~\ref{sec:model}.

\subsection{Hawkes Processes}
\label{sec:background}

Hawkes processes are a class of multivariate self-exciting temporal point
processes originally introduced by Alan G. Hawkes in the early 1970s (CITE) and
have since been used to model a wide range of phenomena ranging from seismic
events to information spread in social networks to stock market trading
dynamics.

In a Hawkes process, the conditional intensity function at any given time $t$
(\emph{i.e} the instantaneous probability of occurrence of an event) can be
written as the sum of a constant exogenous intensity and endogenous
time-varying intensities for the events preceding time $t$.

Formally, for a $D$ dimensional Hawkes process, let us introduce the set of
events $\{(t_i, k_i)\}_{1\leq i \leq N}$ where $t_i$ denotes the time of event
$i$ and $k_i$ the dimension (or coordinate) on which it occurs. The conditional
intensity function is defined as follows:
\begin{equation}
    \label{eq:hawkes}
    \lambda_k(t) = \mu_k + \sum_{i=1}^N \phi_{k_i, k}(t-t_i),
    \quad 1\leq k\leq D
\end{equation}
where $M = (\mu_k)_{1\leq k\leq D}$ is the vector of exogenous intensities and
the functions $\Phi = (\phi_{i,j})_{1\leq i, j\leq D}$ is the matrix of kernel
functions (also known as exciting functions). For a pair of coordinates $(i,
j)$, $\phi_{i,j}$ models the temporal variations of the influence of coordinate
$i$ over coordinate $j$. The kernel functions are \emph{(i)} positive:
$\phi_{i,j}(t)\geq 0$ and \emph{(ii)} causal: $\phi_{i,j}(t) = 0$ whenever
$t<0$. In particular, this implies that the summation in \eqref{eq:hawkes}
is only over the indices $i$ such that $t_i< t$.

We refer the reader to (CITE) for a formal definition of the conditional
intensity function. We will simply use the following formula for the
log-likelihood of events $\mathcal{E} = \{(t_i, k_i)\}_{1\leq i\leq N}$ given
$M$ and $\Phi$ and observation period $[0, T]$:
\begin{equation}
    \label{eq:likelihood}
    \mathcal{L}(\mathcal{E}\given M, \Phi) = \sum_{i=1}^N \log\lambda_{k_i}(t_i)
    - \sum_{k=1}^D\int_{0}^T \lambda_k(t)
\end{equation}

\subsection{Contagion of Gun Violence as a Hawkes Process}
\label{sec:model}

We model the contagion of gun violence as a Hawkes Process by making the
following identifications: each network vertex (\emph{i.e} each individual) is
a coordinate of the Hawkes Process and each gunshot injury is an event of the
process occurring on a coordinate of the process, the victim of the injury.

\paragraph{Exogenous intensity.}

The background rate $\mu(t)$ captures the seasonal rates of violence observed in the data. Given the regularity with which broad rates of violence fluctuate, we assume this process occurs exogenously and is not solely driven by peer contagion. We fit a time-varying function to the data, as described in Section SX.X).

\paragraph{Exciting functions.}

\begin{comment}
We define an instantaneous infection rate that is a variant of the traditional one presented in Equation~\ref{eq:rate}. In particular, we define a unique infection rate for each network vertex $v$.
\begin{equation}
\lambda_v(t) = \underbrace{\mu(t)}_\text{background} + \underbrace{\sum_{u \in V} \Lambda_{uv}(t)}_\text{peer infection}
\end{equation}
\end{comment}


The infection intensity function $\Lambda_{uv}(t)$ models the effect of person $u$ on person $v$ at time $t$. It is based on two common assumptions regarding the spread of contagions.
\begin{enumerate}
\item Time: Consistent with previous models used to infer the spread of contagions over social networks (4, 5), we assume that the impact of earlier infections on future events decays as the time passed since the original infection increases. Additionally, influence can only travel forward in time: an infection has no impact on those that came before it. We assume that influence decays over time based on the distribution $p_t(u,v)=e^{-\beta(t_v-t_u)}$.
\item Network Structure: Epidemiologists commonly assume that contagious events are localized and that the transmission probability increases closer to the source (CITE). In our case, we assume that violence is more likely to spread between people who are more closely linked in the network and measure the distance between individuals based on network topology. Based on previous studies of violence in social networks, we assume that infections are able to occur across a distance of up to three degrees (6); people who are further away in the network have no effect on one another. We assume that influence decays over the network based on the distribution $p_s(u,v)=e^{-\alpha \cdot \text{dist}(u,v)}$.
\end{enumerate}

Combining these two components, we 
\begin{equation}
\Lambda_{uv}(t) = p_s(u,v) p_t(u,v)= \frac{\alpha}{\text{dist}(u,v)} e^{-\beta(t_v-t_u)}
\end{equation}

\subsubsection{Likelihood}
With our infection rate fully-defined, we can now formulate the likelihood function 

\begin{figure}
\centering
\includegraphics{hawkes-diagram}
\caption{Diagram of a Hawkes process. STILL NEED TO MAKE A FIGURE.}
\label{fig:hawkes-diagram}
\end{figure}

\section{Model Inference}

\subsection{Background rate}

Because the seasonal variations in gunshot rates (Figure SX) remain consistent throughout the study period, we assume these are inherent to the infection process and not purely driven by noise or social contagion. Instead of having a constant background rate, we capture seasonal variations as a periodic sinusoidal function. We first compute the aggregate background rate of all the nodes, based on the number of infections each day.

\begin{equation}
M(t) = \mu_0 + A \sin(\omega t + \phi)
\end{equation}

Because we are modeling annual fluctuations, we know that the period is one year, i.e. $\omega=2\pi/365.24$. We learn the other three parameters using non-linear least squares estimates with the Gauss-Newton algorithm. This yields 

\begin{equation}
M(t) = 3.78 + 1.63 \sin(\frac{2\pi}{365.24} t + 4.36)
\end{equation}

\begin{figure}
\centering
\includegraphics{background}
\caption{The background rate $M(t)$ learned to describe the data. Each dot represents the number of infections (fatal and nonfatal) that occurred on a given day.}
\label{fig:background}
\end{figure}

Because we do not know \emph{a priori} which infections are due to the background rate versus peer contagion,
can use the rate of fluctuations but not the scale
we cannot use the base rate and amplitude found. 
[set variable for the value, assume linear relationship between base and fluctuations]
$A = a\mu_0$

\begin{align}
M(t) &= \mu_0' + 0.43 \mu_0 \sin\left(\frac{2\pi}{365.24} t + 4.36\right) \\
     &= \mu_0' \left[1 + 0.43 \sin\left(\frac{2\pi}{365.24} t + 4.36\right) \right]
\end{align}


Finally, we convert the aggregate background rate $M(t)$ to an individual background rate $\mu(t)$ for each person. To do this, note that the aggregate number of shootings in a given day is the sum of each person's instantaneous rate over the course of that day, i.e.
\begin{align}
M(t) &= \sum_{v} \int_{t-1}^{t} \mu(t') dt' \\
     &= |V| \int_{t-1}^{t} \mu(t') dt'
\end{align}

To simplify this calculation, we assume that the individual background rate for each person is constant over the course of a day, i.e. $\int_{t-1}^{t} \mu(t') dt' = \mu(t)$.
[explain why this doesn't really affect results]
This yields the result

\begin{align}
\mu(t) &= \frac{M(t)}{|V|} \\
       &= \frac{\mu_0'}{|V|} \left[1 + 0.43 \sin\left(\frac{2\pi}{365.24} t + 4.36\right) \right] \\
       &= \mu_0 \left[1 + 0.43 \sin\left(\frac{2\pi}{365.24} t + 4.36\right) \right]
\end{align}
where $\mu_0=\mu_0'/|V|$.

\subsection{Kernel function parameters}

We learn parameters using

$\mu_0 = 1.1845e-05$, $\alpha = 0.00317$, and $\beta = 0.0039$.

\begin{equation}
\lambda_v(t) = 1.1845\e{-5} \left[1 + 0.43 \sin\left(\frac{2\pi}{365.24} t + 4.36\right) \right] + \sum_{u \in V} \frac{0.00317}{\text{dist}(u,v)} 0.0039 e^{-0.0039(t-t_u)}
\end{equation}

\section{Inferring infections}
[how we determine background vs peer infection]

We can estimate if a person was primarily infected via peer contagion by comparing the contributions from the background rate and from his or her peers.

We take this approach one step further to determine the person most responsible for infecting each of these 7,016 individuals infected by social contagion.

\begin{figure}
\centering
\includegraphics[width=.6\textwidth]{cascade-distribution}
\caption{The distribution of cascade sizes follows a power-law distribution.}
\label{fig:cascade-sizes}
\end{figure}

\subsection{Experiments with synthetic data}

\subsubsection{Generating networks}
Given that we do not know the true pattern of infection propagation in criminal networks, we first verify that our methods can accurately infer cascades in cases where we do have ground truth data. To test our methods, we generated a series of cascades on social networks. We then had our model determine optimal parameters and use these to guess how each infection spread. We show that our model is able to accurately determine the contagion’s parameters and to identify the path that infections took through social networks.

We first generated network structures using the forest fire model (CITE), which is known to capture the degree distribution and community structure observed in empirical social networks. We generated networks with 10,000 nodes and burning probabilities $p=r=0.3$.

We also simulated contagions on the co-offending network. Since we are most interested in ultimately understanding the diffusion process of violence on the co-offending network, it is important to first test our cascade inference algorithm here and ensure that we are able to accurately recover cascades. We removed all victim and demographic information, leaving just the network structure, and generated contagions. As shown below, we are able to accurately infer the process by which cascades spread on this network.

\subsubsection{Simulating contagions}

\subsubsection{Results}

\section{Regarding causality [THIBAUT WRITE THIS SECTION]}

\end{document}