diff options
Diffstat (limited to 'paper/sections/intro.tex')
| -rw-r--r-- | paper/sections/intro.tex | 23 |
1 files changed, 11 insertions, 12 deletions
diff --git a/paper/sections/intro.tex b/paper/sections/intro.tex index bbbed11..d52da66 100644 --- a/paper/sections/intro.tex +++ b/paper/sections/intro.tex @@ -73,34 +73,33 @@ over a decade \cite{Nowell08} \cite{Leskovec07} \cite{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 recovery guarantees beside empirical validation on synthetic -networks. \cite{Netrapalli:2012} studied the discrete-time version of the +known to have any theoretical guarantees beside empirical validation on synthetic +networks. \citet{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. The algorithm is based around the same -likelihood function we suggest, without the $\ell_1$-norm penalty. Their +recovery guarantee on general networks. The algorithm is based on a +likelihood function similar to the one we propose, without the $\ell_1$-norm penalty. Their analysis depends on 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 matches the ${\cal O}(s \log m)$ guarantee in the case -of tree graphs. The work of \cite{Abrahao:13} study the same continuous-model framework as -\cite{GomezRodriguez:2010} and obtain a ${\cal O}(s^9 \log^2 s \log m)$ support -recovery algorithm without the \emph{correlation decay} assumption. +Greedy} algorithm, which achieves an ${\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. \begin{comment} They assume a single-source model, where only one source is selected at random, which is less realistic in practice since `patient 0' is rarely unknown to us. \end{comment} -Closest to this work is a recent paper by \cite{Daneshmand:2014}, wherein they +Closest to this work is a recent paper by \citet{Daneshmand:2014}, wherein the authors consider a $\ell_1$-regularized objective function. They adapt standard results -from sparse recovery to obtain a recovery bound of ${\cal O}(s^3 \log m)$ on -their algorithm under an irrepresentability condition. Under stronger +from sparse recovery to obtain a recovery bound of ${\cal O}(s^3 \log m)$ under an irrepresentability condition \cite{Zhao:2006}. Under stronger assumptions, they match the \cite{Netrapalli:2012} bound of ${\cal O}(s^2 \log m)$, by exploiting similar properties of the convex program's KKT conditions. In contrast, our work studies discrete-time diffusion processes including the Independent Cascade model under weaker assumptions. Furthermore, we analyze both the recovery of the graph's edges and the estimation of the model's -parameters and achieve close to optimal bounds. +parameters, and achieve closer to optimal bounds. \begin{comment} Their work has the merit of studying a generalization of the discrete-time independent cascade model to continuous functions. Similarly to \cite{Abrahao:13}, they place themselves in |