related works

1 files changed, 36 insertions, 1 deletions

diff --git a/notes/reportYaron.tex b/notes/reportYaron.tex
index d5822ed..be356d2 100644
--- a/notes/reportYaron.tex
+++ b/notes/reportYaron.tex
@@ -21,6 +21,21 @@ Given a set of observed cascades, the \textbf{graph reconstruction problem} cons
 
 There have been several works tackling the graph reconstruction problem in variants of the independent cascade. We briefly summarize their results and approaches below.
 
+\begin{itemize}
+\item Manuel Gomez-Rodriguez, Jure Leskovec, and Andreas Klause were amongst the first to tackle the problem of graph reconstruction from cascade observation \cite{gomez}. Their first method \textsc{NetInf}, and a series of other similar methods published subsequently, solves a heuristic which approximates a NP-hard maximum-likelihood formulation. Unfortunately \textsc{NetInf} has no known theoretical guarantees. One difficulty with comparing ourselves to their heuristic is that they assume a continuous time independent cascade model, which is close but un-adaptable to our framework. Namely, as we will see in Section~\ref{sec:icc}, nodes in our model cannot influence nodes beyond the time step at which they are active.
+\item Their paper was later followed by a publication from Praneeth Netrapalli and Sujay Sanghavi \cite{netrapalli}, which provided two algorithms with several theoretical guarantees. 
+  \begin{itemize}
+  \item The first algorithm they discuss is a convex and parallelizable optimization problem. However, the theoretical guarantee is close to perfect reconstruction of `strong' edges after ${\cal O}(d^2 \log n)$ with high probability. There are several problems to this result however.
+  \begin{itemize}
+  \item Researchers believe the true threshold of cascades necessary is closer to ${\cal O}(d \log n)$
+  \item The constant in the big ${\cal O}$ is highly polynomial in the different constants, of the order of billions even for very generous initializations of these parameters
+  \item The authors make a highly restrictive assumption on the probabilities of each edge, which they call `correlation decay': $\forall i, \sum_{j \in {\cal N}(i)} p_{j,i} < 1 -\alpha$, where $0 < \alpha < 1$
+  \end{itemize}
+  \item The second algorithm, to which we will compare ourselves in Section~\ref{sec:exp}
+  \end{itemize}
+\item 
+\end{itemize}
+
 
 
 \section{The Voter Model}
@@ -123,7 +138,7 @@ b_1  = &  \left( \begin{array}{c}
 \end{align*}
 
 \section{The Independent Cascade Model}
-
+\label{sec:icc}
 \subsection{Description}
 
 In the independent cascade model, nodes have three possible states: susceptible, infected or active\footnote{The words `infected' and `active' are used interchangeably}, and inactive. All nodes start either as susceptible or infected. The infected nodes at $t=0$ constitute the seed set. Similarly to the voter model, we will suppose that nodes are part of the seed set with independent probability $p_{\text{init}}$. At each time step $t$, for every pair of nodes $(j,i)$ where $j$ is infected and $i$ is susceptible, $j$ attempts to infect $i$ with probability $p_{j,i}$. If $j$ succeeds, $i$ will become active at time step $t+1$. Regardless of $j$'s success, node $j$ will be inactive at time $t+1$: nodes stay active for only one time step. The cascade continues until time step $T_k$ when no active nodes remain.
@@ -245,6 +260,7 @@ In general, the smaller $\delta_k$ is, the better we can recover $k$-sparse vect
 \end{itemize}
 
 \section{Experiments}
+\label{sec:exp}
 
 \subsection{Verifying the RIP constants}
 
@@ -288,6 +304,25 @@ The results of our findings on a very small social network (a subset of the famo
 
 \begin{thebibliography}{42}
 
+\bibitem{gomez}
+Gomez-Rodriguez, M., Leskovec, J., and Krause, A.
+\newblock {\it Inferring Networks of Diffusion and Influence}
+\newblock In Proc. 16th ACM SIGKDD international conference on Knowledge discovery and data mining, KDD'10, pages 1019--1028,
+\newblock 2010
+
+\bibitem{netrapalli}
+Netrapalli, P., and Sanghavi, S.,
+\newblock {\it Learning the Graph of Epidemic Cascades}
+\newblock SIGMETRICS Perform. Eval. Rev., 40(1): 211--222,
+\newblock 2012
+
+
+\bibitem{abrahao}
+Abrahao, B., Chierichetti, F., Kleinberg, R., and Panconesi, A.
+\newblock{Trace Complexity of Network Inference}
+\newblock In Proc. 19th ACM SIGKDD international conference on Knowledge discovery and data mingin, KDD'13, pages 491--499,
+\newblock 2013
+
 \bibitem{candestao}
 Candès, E. J., Romberg, J. K., and Tao, T.
 \newblock {\it Stable Signal Recovery from Incomplete and Inaccurate Measurements},