From 97be51465ace29afdea41e9d80fea7b6c344bdda Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Sun, 1 Feb 2015 17:47:12 -0500 Subject: Abstract + first polishing pass over the intro --- paper/sections/abstract.tex | 10 ++++++++++ 1 file changed, 10 insertions(+) create mode 100644 paper/sections/abstract.tex (limited to 'paper/sections/abstract.tex') diff --git a/paper/sections/abstract.tex b/paper/sections/abstract.tex new file mode 100644 index 0000000..9136be7 --- /dev/null +++ b/paper/sections/abstract.tex @@ -0,0 +1,10 @@ +In the Graph Inference problem, one seeks to recover the edges of an unknown +graph from the observations of influence cascades propagating over this graph. +In this paper, we approach this problem from the sparse recovery perspective +and provide an algorithm which recovers the graph edges with high probability +provided that the number of measurements is $\Omega(s\log m)$ 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 provide an almost matching lower bound of +$\Omega(s\log\frac{m}{s})$. -- cgit v1.2.3-70-g09d2