Poster abstract, 40% done

2 files changed, 661 insertions, 5 deletions

diff --git a/poster_abstract/main.tex b/poster_abstract/main.tex
index 45f4aad..5c17bf8 100644
--- a/poster_abstract/main.tex
+++ b/poster_abstract/main.tex
@@ -1,7 +1,34 @@
-\documentclass{sig-alternate-2013}

+\documentclass[a4]{sig-alternate-2013}

+\usepackage[utf8x]{inputenc}

 

+\usepackage{amsmath, amsfonts, amssymb, amsthm, bbm}

+\usepackage{verbatim}

+\newcommand{\reals}{\mathbb{R}}

+\newcommand{\ints}{\mathbb{N}}

+\renewcommand{\O}{\mathcal{O}}

+\DeclareMathOperator{\E}{\mathbb{E}}

+\let\P\relax

+\DeclareMathOperator{\P}{\mathbb{P}}

+\newcommand{\ex}[1]{\E\left[#1\right]}

+\newcommand{\prob}[1]{\P\left[#1\right]}

+\newcommand{\inprod}[2]{#1 \cdot #2}

+\newcommand{\defeq}{\equiv}

+\DeclareMathOperator*{\argmax}{argmax}

+\DeclareMathOperator*{\argmin}{argmin}

 

-\permission{Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage, and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s). Copyright is held by the author/owner(s).}

+\newtheorem{theorem}{Theorem}

+\newtheorem{lemma}{Lemma}

+\newtheorem{corollary}{Corollary}

+\newtheorem{remark}{Remark}

+\newtheorem{proposition}{Proposition}

+\newtheorem{definition}{Definition}

+

+\permission{Permission to make digital or hard copies of part or all of this

+work for personal or classroom use is granted without fee provided that copies

+are not made or distributed for profit or commercial advantage, and that copies

+bear this notice and the full citation on the first page. Copyrights for

+third-party components of this work must be honored. For all other uses,

+contact the owner/author(s).  Copyright is held by the author/owner(s).}

 \conferenceinfo{WWW 2015 Companion,}{May 18--22, 2015, Florence, Italy.}

 \copyrightetc{ACM \the\acmcopyr}

 \crdata{978-1-4503-3473-0/15/05. \\

@@ -11,7 +38,6 @@ http://dx.doi.org/10.1145/2740908.2744107}
 \widowpenalty = 10000

 

 \title{Inferring Graphs from Cascades:\\ A Sparse Recovery Framework}

-\subtitle{[Extended Abstract]

 %\titlenote{A full version of this paper is available as \textit{Author's Guide to Preparing ACM SIG Proceedings Using \LaTeX$2_\epsilon$\ and BibTeX} at \texttt{www.acm.org/eaddress.htm}}}

 

 \numberofauthors{2}

@@ -31,16 +57,143 @@ Thibaut Horel\\
 \maketitle

 

 \begin{abstract}

+In the Graph Inference problem, one seeks to recover the edges of an unknown

+graph from the observations of cascades propagating over this graph.  We

+approach this problem from the sparse recovery perspective.  We introduce

+a general model of cascades, including the voter model and the independent

+cascade model, for which we provide the first algorithm which recovers the

+graph's edges with high probability and ${\cal O}(s\log m)$ measurements where

+$s$ is the maximum degree of the graph and $m$ is the number of nodes.

+Furthermore, we show that our algorithm also recovers the edge weights (the

+parameters of the diffusion process) and is robust in the context of

+approximate sparsity. Finally we prove an almost matching lower bound of

+$\Omega(s\log\frac{m}{s})$ and validate our approach empirically on synthetic

+graphs.

 \end{abstract}

 

 \category{I.2.6}{Artificial Intelligence}{Learning}[Parameter Learning]

 \terms{Theory, Performance, Measurements}

 \keywords{Graph Inference; Cascades; Sparse Recovery}

 

+\section{Introduction}

+

+A recent line of research has focused on the Graph Inference Problem:

+recovering the edges of an unknown graph from the observations of a diffusion

+process propagating on this graph \cite{Netrapalli:2012} CITE. The Independent

+Cascade Model CITE is a famous example of such a diffusion process where the

+edges between a given vertex and its parents are weighted; the weights are

+parameters of the model and capture how much influence a parent vertex has over

+its child vertex.

+

+Here, we propose a sparse recovery framework to not only solve the Graph

+Inference Problem, but also recover the unknown weights of the diffusion

+process. The parallel with sparse recovery problems is as follows: for a given

+vertex, the signal to recover is a vector of weights, the “influence” of its

+(unknown) parents in the graph. This signal is observed indirectly through

+instances of the diffusion process: the only thing known to the observer are

+the time steps at which the vertices in the graph become “infected” by the

+diffusion process. The two main challenges to apply sparse recovery tools to

+this problem are: (1) contrary to a very common assumption, the measurements

+given by a diffusion process are correlated (2) most diffusion processes lead

+to non-linear sparse recovery problems.

+

+In what follows, we first present a general class of discrete-time diffusion

+processes which encompasses the Influence Cascade Model and the Voter Model

+CITE. For this class of diffusion processes, despite the afore-mentioned

+challenges, we show how to recover the unknown parameters with a convergence

+rate $O(s\log m/\sqrt{n})$ where $s$ is the in-degree of a given vertex, $m$ is

+the number of vertices in the graph and $n$ is the number of observations. In

+particular, given $\Omega(s\log m)$ measurements, we are able to recover the

+edges of the graph. Finally, we validate our approach experimentally, by

+comparing its performance to state of the art algorithms on synthetic data.

+

+\section{Model}

+

+Let consider a graph $G = (V, E)$ with $|V|= m$ and where the set of edges $E$

+is unknown. For a given vertex $j$, the cascade model is parametrized by

+a vector $\theta_j\in\reals^m$ where the $i$-th coordinate of $\theta_j$

+captures the “influence” of vertex $i$ on $j$. This influence is 0 if $i$ is

+not a parent of $j$.

+

+A cascade is characterized by the propagation of a “contagious” state in

+discrete time steps. Initially, each vertex is contagious with probability

+$p_{\text{init}}$. Let us denote by $X^0$ the indicator vector of the initially

+contagious vertices.

+Denoting by $X^t$ the indicator vector of the set of

+vertices which are contagious at time step $t$, the probability that $j$ will

+be contagious at time $t+1$ is given by:

+\begin{equation}

+    \label{eq:glm}

+    \mathbb{P}(X^{t+1}_j = 1|X^t) 

+    = f(\theta_j \cdot X^t)

+\end{equation}

+where $f: \reals \rightarrow [0,1]$. Conditioned on $X^t$, this

+evolution happens independently for each vertex at time $t+1$.

+

+DO WE HAVE ENOUGH SPACE FOR EXAMPLES HERE?

+

+\section{Results}

+

+For a given vertex $i$, we are given a set of measurements, $(X^t,

+X^{t+1}_i)_{t\in\mathcal{T}_i}$ generated from \eqref{eq:glm}. We estimate

+$\theta_i$ via $\ell_1$-regularized maximum likelihood estimation:

+\begin{equation}\label{eq:pre-mle}

+    \hat{\theta}_i \in \argmax_{\theta} \mathcal{L}_i(\theta_i\,|\,x^1,\ldots,x^n)

+    - \lambda\|\theta_i\|_1

+\end{equation}

+where $\mathcal{L}_i$ is the log-likelihood of $\theta_i$ given the

+observations:

+\begin{multline*}

+    \mathcal{L}_i(\theta_i\,|\,x^1,\ldots,x^n) = \frac{1}{|{\cal T}_i|}

+    \sum_{t\in {\cal T}_i } x_i^{t+1}\log f(\inprod{\theta_i}{x^{t}}) \\

+    + (1 - x_i^{t+1})\log\big(1-f(\inprod{\theta_i}{x^t})\big)

+\end{multline*}

+

+We will need the following assumptions:

+\begin{enumerate}

+    \item $\log f$ and $\log (1-f)$ are concave functions.

+    \item $\log f$ and $\log (1-f)$ have derivatives bounded in absolute value

+        by $\frac{1}{\alpha}$ for some $\alpha > 0$.

+    \item denoting by $S$ the support of the true vector of parameters

+        $\theta_i^*$, define $\mathcal{C}(S)\defeq

+    \{X\in\reals^m\,:\,\|X\|_1\leq 1\text{ and } \|X_{S^c}\|_1\leq

+    3\|X_S\|_1\}$. We assume that:

+\begin{equation*}

+    \forall X \in {\cal C(S)}, X^T \nabla^2\mathcal{L}_i(\theta_i^*)X

+    \geq \gamma \|X\|_2^2 

+\end{equation*}

+for some $\gamma>0$.

+\end{enumerate}

+

+\begin{theorem}

+\label{thm:main}

+Assume 1. to 3. above and define $n\defeq |\mathcal{T}_i|$. For any

+$\delta\in(0,1)$, let $\hat{\theta_i}$ be the solution of \eqref{eq:pre-mle}

+with $\lambda \defeq 2\sqrt{\frac{\log m}{\alpha n^{1 - \delta}}}$, then:

+\begin{equation}

+    \label{eq:sparse}

+    \|\hat \theta_i - \theta^*_i \|_2

+    \leq \frac{6}{\gamma} \sqrt{\frac{s \log m}{\alpha n^{1-\delta}}}

+\quad

+\text{w.p.}\;1-\frac{1}{e^{n^\delta \log m}}

+\end{equation}

+\end{theorem}

+

+Assumption 3. above can be replaced by the following data-independent

+assumption:

+\begin{enumerate}

+    \item[3.] $\log f$ and $\log (1-f)$ are $\varepsilon$-concave and the

+        expected Hessian $H = \lim_{n\rightarrow\infty\frac{1}{n}X^TX}$ has

+        a smallest eigenvalue bounded from below by $\gamma>0$, where $X$ is

+        the $n\times m$ design matrix whose $k$-th row is $X^k$.

+\end{enumerate}

+at the cost of slightly reduced convergence rate:

+\section{Experiments}

+

 %\section{Acknowledgments}

 

-%\bibliographystyle{abbrv}

-%\bibliography{sigproc}

+\bibliographystyle{abbrv}

+\bibliography{sparse}

 

 %\balancecolumns

 \end{document}

diff --git a/poster_abstract/sparse.bib b/poster_abstract/sparse.bib
new file mode 100644
index 0000000..5df4b59
--- /dev/null
+++ b/poster_abstract/sparse.bib
@@ -0,0 +1,503 @@
+@article {CandesRomberTao:2006,
+author = {Candès, Emmanuel J. and Romberg, Justin K. and Tao, Terence},
+title = {Stable signal recovery from incomplete and inaccurate measurements},
+journal = {Communications on Pure and Applied Mathematics},
+volume = {59},
+number = {8},
+publisher = {Wiley Subscription Services, Inc., A Wiley Company},
+issn = {1097-0312},
+pages = {1207--1223},
+year = {2006},
+}
+
+
+@inproceedings{GomezRodriguez:2010,
+ author = {Gomez Rodriguez, Manuel and Leskovec, Jure and Krause, Andreas},
+ title = {Inferring Networks of Diffusion and Influence},
+ booktitle = {Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
+ series = {KDD '10},
+ year = {2010},
+ isbn = {978-1-4503-0055-1},
+ location = {Washington, DC, USA},
+ pages = {1019--1028},
+ numpages = {10},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+} 
+
+
+@article{Netrapalli:2012,
+ author = {Netrapalli, Praneeth and Sanghavi, Sujay},
+ title = {Learning the Graph of Epidemic Cascades},
+ journal = {SIGMETRICS Perform. Eval. Rev.},
+ volume = {40},
+ number = {1},
+ month = {June},
+ year = {2012},
+ issn = {0163-5999},
+ pages = {211--222},
+ numpages = {12},
+ publisher = {ACM},
+ address = {New York, NY, USA},
+ keywords = {cascades, epidemics, graph structure learning},
+}
+
+@article{Negahban:2009,
+ author = {Negahban, Sahand N. and Ravikumar, Pradeep and Wrainwright, Martin J. and Yu, Bin},
+ title = {A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers},
+ Journal = {Statistical Science},
+ year = {2012},
+ month = {December},
+ volume = {27},
+ number = {4},
+ pages = {538--557},
+}
+
+@article{Zhao:2006,
+ author = {Zhao, Peng and Yu, Bin},
+ title = {On Model Selection Consistency of Lasso},
+ journal = {J. Mach. Learn. Res.},
+ issue_date = {12/1/2006},
+ volume = {7},
+ month = dec,
+ year = {2006},
+ issn = {1532-4435},
+ pages = {2541--2563},
+ numpages = {23},
+ url = {http://dl.acm.org/citation.cfm?id=1248547.1248637},
+ acmid = {1248637},
+ publisher = {JMLR.org},
+} 
+
+@inproceedings{Daneshmand:2014,
+  author    = {Hadi Daneshmand and
+               Manuel Gomez{-}Rodriguez and
+               Le Song and
+               Bernhard Sch{\"{o}}lkopf},
+  title     = {Estimating Diffusion Network Structures: Recovery Conditions, Sample
+               Complexity {\&} Soft-thresholding Algorithm},
+  booktitle = {Proceedings of the 31th International Conference on Machine Learning,
+               {ICML} 2014, Beijing, China, 21-26 June 2014},
+  pages     = {793--801},
+  year      = {2014},
+  url       = {http://jmlr.org/proceedings/papers/v32/daneshmand14.html},
+  timestamp = {Fri, 07 Nov 2014 20:42:30 +0100},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/icml/DaneshmandGSS14},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@inproceedings{Kempe:03,
+  author    = {David Kempe and
+               Jon M. Kleinberg and
+               {\'{E}}va Tardos},
+  title     = {Maximizing the spread of influence through a social network},
+  booktitle = {Proceedings of the Ninth {ACM} {SIGKDD} International Conference on
+               Knowledge Discovery and Data Mining, Washington, DC, USA, August 24
+               - 27, 2003},
+  pages     = {137--146},
+  year      = {2003},
+  url       = {http://doi.acm.org/10.1145/956750.956769},
+  doi       = {10.1145/956750.956769},
+  timestamp = {Mon, 13 Feb 2006 15:34:20 +0100},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/kdd/KempeKT03},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@inproceedings{Abrahao:13,
+  author    = {Bruno D. Abrahao and
+               Flavio Chierichetti and
+               Robert Kleinberg and
+               Alessandro Panconesi},
+  title     = {Trace complexity of network inference},
+  booktitle = {The 19th {ACM} {SIGKDD} International Conference on Knowledge Discovery
+               and Data Mining, {KDD} 2013, Chicago, IL, USA, August 11-14, 2013},
+  pages     = {491--499},
+  year      = {2013},
+  url       = {http://doi.acm.org/10.1145/2487575.2487664},
+  doi       = {10.1145/2487575.2487664},
+  timestamp = {Tue, 10 Sep 2013 10:11:57 +0200},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/kdd/AbrahaoCKP13},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+
+@article{vandegeer:2009,
+author = "van de Geer, Sara A. and B{\"u}hlmann, Peter",
+doi = "10.1214/09-EJS506",
+fjournal = "Electronic Journal of Statistics",
+journal = "Electron. J. Statist.",
+pages = "1360--1392",
+publisher = "The Institute of Mathematical Statistics and the Bernoulli Society",
+title = "On the conditions used to prove oracle results for the Lasso",
+url = "http://dx.doi.org/10.1214/09-EJS506",
+volume = "3",
+year = "2009"
+}
+
+@article{vandegeer:2011,
+author = "van de Geer, Sara and Bühlmann, Peter and Zhou, Shuheng",
+doi = "10.1214/11-EJS624",
+fjournal = "Electronic Journal of Statistics",
+journal = "Electron. J. Statist.",
+pages = "688--749",
+publisher = "The Institute of Mathematical Statistics and the Bernoulli Society",
+title = "The adaptive and the thresholded Lasso for potentially misspecified models (and a lower bound for the Lasso)",
+url = "http://dx.doi.org/10.1214/11-EJS624",
+volume = "5",
+year = "2011"
+}
+
+@article{Zou:2006,
+author = {Zou, Hui},
+title = {The Adaptive Lasso and Its Oracle Properties},
+journal = {Journal of the American Statistical Association},
+volume = {101},
+number = {476},
+pages = {1418-1429},
+year = {2006},
+doi = {10.1198/016214506000000735},
+URL = {http://dx.doi.org/10.1198/016214506000000735},
+}
+
+@article{Jacques:2013,
+  author    = {Laurent Jacques and
+               Jason N. Laska and
+               Petros T. Boufounos and
+               Richard G. Baraniuk},
+  title     = {Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse
+               Vectors},
+  journal   = {{IEEE} Transactions on Information Theory},
+  volume    = {59},
+  number    = {4},
+  pages     = {2082--2102},
+  year      = {2013},
+  url       = {http://dx.doi.org/10.1109/TIT.2012.2234823},
+  doi       = {10.1109/TIT.2012.2234823},
+  timestamp = {Tue, 09 Apr 2013 19:57:48 +0200},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/tit/JacquesLBB13},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@inproceedings{Boufounos:2008,
+  author    = {Petros Boufounos and
+               Richard G. Baraniuk},
+  title     = {1-Bit compressive sensing},
+  booktitle = {42nd Annual Conference on Information Sciences and Systems, {CISS}
+               2008, Princeton, NJ, USA, 19-21 March 2008},
+  pages     = {16--21},
+  year      = {2008},
+  url       = {http://dx.doi.org/10.1109/CISS.2008.4558487},
+  doi       = {10.1109/CISS.2008.4558487},
+  timestamp = {Wed, 15 Oct 2014 17:04:27 +0200},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/ciss/BoufounosB08},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@inproceedings{Gupta:2010,
+  author    = {Ankit Gupta and
+               Robert Nowak and
+               Benjamin Recht},
+  title     = {Sample complexity for 1-bit compressed sensing and sparse classification},
+  booktitle = {{IEEE} International Symposium on Information Theory, {ISIT} 2010,
+               June 13-18, 2010, Austin, Texas, USA, Proceedings},
+  pages     = {1553--1557},
+  year      = {2010},
+  url       = {http://dx.doi.org/10.1109/ISIT.2010.5513510},
+  doi       = {10.1109/ISIT.2010.5513510},
+  timestamp = {Thu, 15 Jan 2015 17:11:50 +0100},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/isit/GuptaNR10},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@article{Plan:2014,
+  author    = {Yaniv Plan and
+               Roman Vershynin},
+  title     = {Dimension Reduction by Random Hyperplane Tessellations},
+  journal   = {Discrete {\&} Computational Geometry},
+  volume    = {51},
+  number    = {2},
+  pages     = {438--461},
+  year      = {2014},
+  url       = {http://dx.doi.org/10.1007/s00454-013-9561-6},
+  doi       = {10.1007/s00454-013-9561-6},
+  timestamp = {Tue, 11 Feb 2014 13:48:56 +0100},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/dcg/PlanV14},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@article{bickel:2009,
+author = "Bickel, Peter J. and Ritov, Ya’acov and Tsybakov, Alexandre B.",
+doi = "10.1214/08-AOS620",
+fjournal = "The Annals of Statistics",
+journal = "Ann. Statist.",
+month = "08",
+number = "4",
+pages = "1705--1732",
+publisher = "The Institute of Mathematical Statistics",
+title = "Simultaneous analysis of Lasso and Dantzig selector",
+url = "http://dx.doi.org/10.1214/08-AOS620",
+volume = "37",
+year = "2009"
+}
+
+@article{raskutti:10,
+  author    = {Garvesh Raskutti and
+               Martin J. Wainwright and
+               Bin Yu},
+  title     = {Restricted Eigenvalue Properties for Correlated Gaussian Designs},
+  journal   = {Journal of Machine Learning Research},
+  volume    = {11},
+  pages     = {2241--2259},
+  year      = {2010},
+  url       = {http://portal.acm.org/citation.cfm?id=1859929},
+  timestamp = {Wed, 15 Oct 2014 17:04:32 +0200},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/jmlr/RaskuttiWY10},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@article{rudelson:13,
+  author    = {Mark Rudelson and
+               Shuheng Zhou},
+  title     = {Reconstruction From Anisotropic Random Measurements},
+  journal   = {{IEEE} Transactions on Information Theory},
+  volume    = {59},
+  number    = {6},
+  pages     = {3434--3447},
+  year      = {2013},
+  url       = {http://dx.doi.org/10.1109/TIT.2013.2243201},
+  doi       = {10.1109/TIT.2013.2243201},
+  timestamp = {Tue, 21 May 2013 14:15:50 +0200},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/tit/RudelsonZ13},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@article{bipw11,
+  author    = {Khanh Do Ba and
+               Piotr Indyk and
+               Eric Price and
+               David P. Woodruff},
+  title     = {Lower Bounds for Sparse Recovery},
+  journal   = {CoRR},
+  volume    = {abs/1106.0365},
+  year      = {2011},
+  url       = {http://arxiv.org/abs/1106.0365},
+  timestamp = {Mon, 05 Dec 2011 18:04:39 +0100},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/corr/abs-1106-0365},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@inproceedings{pw11,
+  author    = {Eric Price and
+               David P. Woodruff},
+  title     = {{(1} + eps)-Approximate Sparse Recovery},
+  booktitle = {{IEEE} 52nd Annual Symposium on Foundations of Computer Science, {FOCS}
+               2011, Palm Springs, CA, USA, October 22-25, 2011},
+  pages     = {295--304},
+  year      = {2011},
+  crossref  = {DBLP:conf/focs/2011},
+  url       = {http://dx.doi.org/10.1109/FOCS.2011.92},
+  doi       = {10.1109/FOCS.2011.92},
+  timestamp = {Tue, 16 Dec 2014 09:57:24 +0100},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/focs/PriceW11},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@proceedings{DBLP:conf/focs/2011,
+  editor    = {Rafail Ostrovsky},
+  title     = {{IEEE} 52nd Annual Symposium on Foundations of Computer Science, {FOCS}
+               2011, Palm Springs, CA, USA, October 22-25, 2011},
+  publisher = {{IEEE} Computer Society},
+  year      = {2011},
+  url       = {http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6108120},
+  isbn      = {978-1-4577-1843-4},
+  timestamp = {Mon, 15 Dec 2014 18:48:45 +0100},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/focs/2011},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@inproceedings{pw12,
+  author    = {Eric Price and
+               David P. Woodruff},
+  title     = {Applications of the Shannon-Hartley theorem to data streams and sparse
+               recovery},
+  booktitle = {Proceedings of the 2012 {IEEE} International Symposium on Information
+               Theory, {ISIT} 2012, Cambridge, MA, USA, July 1-6, 2012},
+  pages     = {2446--2450},
+  year      = {2012},
+  crossref  = {DBLP:conf/isit/2012},
+  url       = {http://dx.doi.org/10.1109/ISIT.2012.6283954},
+  doi       = {10.1109/ISIT.2012.6283954},
+  timestamp = {Mon, 01 Oct 2012 17:34:07 +0200},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/isit/PriceW12},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@proceedings{DBLP:conf/isit/2012,
+  title     = {Proceedings of the 2012 {IEEE} International Symposium on Information
+               Theory, {ISIT} 2012, Cambridge, MA, USA, July 1-6, 2012},
+  publisher = {{IEEE}},
+  year      = {2012},
+  url       = {http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=6268627},
+  isbn      = {978-1-4673-2580-6},
+  timestamp = {Mon, 01 Oct 2012 17:33:45 +0200},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/isit/2012},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@article{Leskovec:2010,
+  author    = {Jure Leskovec and
+               Deepayan Chakrabarti and
+               Jon M. Kleinberg and
+               Christos Faloutsos and
+               Zoubin Ghahramani},
+  title     = {Kronecker Graphs: An Approach to Modeling Networks},
+  journal   = {Journal of Machine Learning Research},
+  volume    = {11},
+  pages     = {985--1042},
+  year      = {2010},
+  url       = {http://doi.acm.org/10.1145/1756006.1756039},
+  doi       = {10.1145/1756006.1756039},
+  timestamp = {Thu, 22 Apr 2010 13:26:26 +0200},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/jmlr/LeskovecCKFG10},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@article{Holme:2002,
+  author= {Petter Holme and Beom Jun Kim},
+  title = {Growing scale-free networks with tunable clustering},
+  journal = {Physical review E},
+  volume = {65},
+  issue = {2},
+  pages = {026--107},
+  year = {2002}
+}
+
+
+@article{watts:1998,
+  Annote = {10.1038/30918},
+  Author = {Watts, Duncan J. and Strogatz, Steven H.},
+  Date = {1998/06/04/print},
+  Isbn = {0028-0836},
+  Journal = {Nature},
+  Number = {6684},
+  Pages = {440--442},
+  Read = {0},
+  Title = {Collective dynamics of `small-world' networks},
+  Url = {http://dx.doi.org/10.1038/30918},
+  Volume = {393},
+  Year = {1998},
+}
+
+@article{barabasi:2001,
+  author    = {R{\'{e}}ka Albert and
+               Albert{-}L{\'{a}}szl{\'{o}} Barab{\'{a}}si},
+  title     = {Statistical mechanics of complex networks},
+  journal   = {CoRR},
+  volume    = {cond-mat/0106096},
+  year      = {2001},
+  url       = {http://arxiv.org/abs/cond-mat/0106096},
+  timestamp = {Mon, 05 Dec 2011 18:05:15 +0100},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/corr/cond-mat-0106096},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+
+@article{gomezbalduzzi:2011,
+  author    = {Manuel Gomez{-}Rodriguez and
+               David Balduzzi and
+               Bernhard Sch{\"{o}}lkopf},
+  title     = {Uncovering the Temporal Dynamics of Diffusion Networks},
+  journal   = {CoRR},
+  volume    = {abs/1105.0697},
+  year      = {2011},
+  url       = {http://arxiv.org/abs/1105.0697},
+  timestamp = {Mon, 05 Dec 2011 18:05:23 +0100},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/corr/abs-1105-0697},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@article{Nowell08,
+  author = {Liben-Nowell, David and Kleinberg, Jon},
+  biburl = {http://www.bibsonomy.org/bibtex/250b9b1ca1849fa9cb8bb92d6d9031436/mkroell},
+  doi = {10.1073/pnas.0708471105},
+  eprint = {http://www.pnas.org/content/105/12/4633.full.pdf+html},
+  journal = {Proceedings of the National Academy of Sciences},
+  keywords = {SNA graph networks},
+  number = 12,
+  pages = {4633-4638},
+  timestamp = {2008-10-09T10:32:56.000+0200},
+  title = {{Tracing information flow on a global scale using Internet chain-letter data}},
+  url = {http://www.pnas.org/content/105/12/4633.abstract},
+  volume = 105,
+  year = 2008
+}
+
+@inproceedings{Leskovec07,
+  author    = {Jure Leskovec and
+               Mary McGlohon and
+               Christos Faloutsos and
+               Natalie S. Glance and
+               Matthew Hurst},
+  title     = {Patterns of Cascading Behavior in Large Blog Graphs},
+  booktitle = {Proceedings of the Seventh {SIAM} International Conference on Data
+               Mining, April 26-28, 2007, Minneapolis, Minnesota, {USA}},
+  pages     = {551--556},
+  year      = {2007},
+  url       = {http://dx.doi.org/10.1137/1.9781611972771.60},
+  doi       = {10.1137/1.9781611972771.60},
+  timestamp = {Wed, 12 Feb 2014 17:08:15 +0100},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/sdm/LeskovecMFGH07},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+
+@inproceedings{AdarA05,
+  author    = {Eytan Adar and
+               Lada A. Adamic},
+  title     = {Tracking Information Epidemics in Blogspace},
+  booktitle = {2005 {IEEE} / {WIC} / {ACM} International Conference on Web Intelligence
+               {(WI} 2005), 19-22 September 2005, Compiegne, France},
+  pages     = {207--214},
+  year      = {2005},
+  url       = {http://dx.doi.org/10.1109/WI.2005.151},
+  doi       = {10.1109/WI.2005.151},
+  timestamp = {Tue, 12 Aug 2014 16:59:16 +0200},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/webi/AdarA05},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@inproceedings{Kleinberg:00,
+  author    = {Jon M. Kleinberg},
+  title     = {The small-world phenomenon: an algorithm perspective},
+  booktitle = {Proceedings of the Thirty-Second Annual {ACM} Symposium on Theory
+               of Computing, May 21-23, 2000, Portland, OR, {USA}},
+  pages     = {163--170},
+  year      = {2000},
+  url       = {http://doi.acm.org/10.1145/335305.335325},
+  doi       = {10.1145/335305.335325},
+  timestamp = {Thu, 16 Feb 2012 12:06:08 +0100},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/stoc/Kleinberg00},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
+
+@article{zhang2014,
+  title={Confidence intervals for low dimensional parameters in high dimensional linear models},
+  author={Zhang, Cun-Hui and Zhang, Stephanie S},
+  journal={Journal of the Royal Statistical Society: Series B (Statistical Methodology)},
+  volume={76},
+  number={1},
+  pages={217--242},
+  year={2014},
+  publisher={Wiley Online Library}
+}
+
+@article{javanmard2014,
+  title={Confidence intervals and hypothesis testing for high-dimensional regression},
+  author={Javanmard, Adel and Montanari, Andrea},
+  journal={The Journal of Machine Learning Research},
+  volume={15},
+  number={1},
+  pages={2869--2909},
+  year={2014},
+  publisher={JMLR. org}
+}