diff options
| -rw-r--r-- | finale/mid_report.tex | 32 |
1 files changed, 30 insertions, 2 deletions
diff --git a/finale/mid_report.tex b/finale/mid_report.tex index e35a839..3a808d5 100644 --- a/finale/mid_report.tex +++ b/finale/mid_report.tex @@ -69,6 +69,35 @@ Two subquestions: faster (use a Bayesian prior)? \end{itemize} +\subsection*{Related work} +The study of edge prediction in graphs has been an active field of research for +over a decade~\cite{Nowell08, Leskovec07, AdarA05}.~\cite{GomezRodriguez:2010} +introduced the {\scshape Netinf} algorithm, which approximates the likelihood of +cascades represented as a continuous process. The algorithm was improved in +later work~\cite{gomezbalduzzi:2011}, but is not known to have any theoretical +guarantees beside empirical validation on synthetic networks. +\cite{Netrapalli:2012} studied the discrete-time version of the independent +cascade model and obtained the first ${\cal O}(s^2 \log m)$ recovery guarantee +on general networks, by using unregularized MLE and making a {\it correlation +decay\/} assumption, which limits the number of new infections at every step. In +this setting, they show a lower bound of the number of cascades needed for +support recovery with constant probability of the order $\Omega(s \log (m/s))$. +They also suggest a {\scshape Greedy} algorithm, which achieves a ${\cal O}(s +\log m)$ guarantee in the case of tree graphs. The work of~\cite{Abrahao:13} +studies the same continuous-model framework as \cite{GomezRodriguez:2010} and +obtains an ${\cal O}(s^9 \log^2 s \log m)$ support recovery algorithm, without +the \emph{correlation decay} assumption. \cite{du2013uncover,Daneshmand:2014} +propose Lasso regularization of MLE for recovering the weights of the graph +under a continuous-time independent cascade model. The work +of~\cite{du2014influence} is slightly orthogonal to ours since they suggest +learning the \emph{influence} function, rather than the parameters of the +network directly. + +More recently, the inference of Hawkes process is perhaps the closest related +topic to our work, with recent papers \cite{linderman2014discovering, +linderman2015scalable} , focusing on MLE, EM, and Variational +Inference methods to learning these processes. + \section{Model} Weighted directed graph $G = (V, \Theta)$. $k=|V|$ is the number of nodes. @@ -95,7 +124,6 @@ Markovian process: $\bt_i$ is the $i$th column of $\Theta$, $f:\R\to[0,1]$, plus independence for $i$. A cascade continues until no more infected nodes. - \section{Identifiability} A given source distribution $p_s$ and \cref{eq:markov} completely specifies the @@ -329,6 +357,6 @@ given $(x_t)_{t\geq1}$}$ \Comment{Update posterior on $\theta$} \end{algorithm} \bibliography{sparse}{} -\bibliographystyle{plain} +\bibliographystyle{alpha} \end{document} |