diff options
Diffstat (limited to 'paper/sections/abstract.tex')
| -rw-r--r-- | paper/sections/abstract.tex | 10 |
1 files changed, 10 insertions, 0 deletions
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})$. |