1 files changed, 171 insertions, 0 deletions
diff --git a/supplements/main.tex b/supplements/main.tex
new file mode 100644
index 0000000..10e1a52
--- /dev/null
+++ b/supplements/main.tex
@@ -0,0 +1,171 @@
+\documentclass{article}
+\usepackage[utf8]{inputenc}
+\usepackage{amsmath}
+\usepackage{algorithm}% http://ctan.org/pkg/algorithms
+\usepackage{algpseudocode}% http://ctan.org/pkg/algorithmicx
+\usepackage{graphicx}
+\DeclareMathOperator*{\argmax}{argmax}
+\providecommand{\e}[1]{\ensuremath{\times 10^{#1}}}
+
+\title{Hawkes contagion model}
+\author{Ben Green \and Thibaut Horel \and Andrew Papachristos}
+\date{September 2015}
+
+\begin{document}
+
+\maketitle
+
+\section{Hawkes contagion model}
+We model the contagion of violence using a multidimensional Hawkes process over the co-offending network.
+
+\subsection{Background}
+We first develop the theory and notation behind the Hawkes process as it is traditionally presented.
+
+The Hawkes process models the instantaneous propensity to become infected at time $t$ based on both exogenous and endogenous factors: a background rate $\mu$ that captures infections unrelated to social interactions and a peer contagion component that considers the social influence of previous infections. The instantaneous infection rate $\lambda(t)$ (also known as the ``hazard function" and ``conditional intensity function") is typically defined as follows:
+\begin{equation}
+\lambda(t) = \mu + \alpha\sum_{t_i < t}e^{-\beta(t-t_i)}
+\end{equation}
+
+More generally, the Hawkes process can be written as
+\begin{equation}\label{eq:rate}
+\lambda(t) = \mu + \sum_{t_u < t_v}p(u,v)
+\end{equation}
+where in the typical case $p(u,v)=\alpha e^{-\beta(t_v-t_u)}$.
+
+Based on the instantaneous infection rate $\lambda(t)$ we can define the probability of certain events. Doing so relies on the following functions:
+\begin{itemize}
+\item Conditional density function $f$: the probability that an infection will occur at a given time.
+\item Cumulative distribution function $F$: the probability that an infection will occur before the current time $t$.
+\item Survival function $S$: the probability that an infection will not have occurred before the current time $t$. This implies that $S = 1 - F$.
+\end{itemize}
+
+We can define the probability of infection at a given time $t$ as the instantaneous infection rate at $t$ multiplied by the probability that the item survived uninfected up until $t$.
+\begin{equation}
+f(t) = \lambda(t) S(t)
+\end{equation}
+
+The survival function is given by
+\begin{equation}
+S(t) = \exp\left(-\int_{t_{last}}^t \lambda(s) ds\right)
+\end{equation}
+where $t_{last}$ is the time of the most recent infection before $t$.
+
+Now we can define 
+\begin{equation}
+f(t) = \lambda(t) \exp\left(-\int_{t_{last}}^t \lambda(s) ds\right)
+\end{equation}
+
+The likelihood is given by the density function for each observed infection and the survival function for all times without an infection. For a Hawkes process over the period $[0,T]$ with $n$ infections, the likelihood is defined as
+\begin{equation}
+L = \left[ f(t_1) \ldots f(t_n) \right] S(T) = \left[\prod_{i=1}^{n} \lambda(t_i) \right] \exp\left(-\int_{0}^{T} \lambda(s) ds \right)
+\end{equation}
+
+\subsection{Our model}
+We extend the single-dimensional Hawkes process to a multi-dimensional variant that can properly describe the contagion process over our network. We utilize a multidimensional approach where each network vertex (i.e. each individual) occupies its own dimension. This allows us to specify the unique set of social influences that each person encounters vis-a-vis his or her pattern of co-offending ties.
+
+\subsubsection{Infection rate}
+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}
+
+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).
+
+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{Caption}
+\label{fig:hawkes-diagram}
+\end{figure}
+
+\subsection{Finding the 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{Caption}
+\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{Learning the parameters [THIBAUT FILL IN THIS SECTION]}
+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}
+
+\subsection{Cascade recovery}
+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.
+
+\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}