diff options
Diffstat (limited to 'paper/sections/abstract.tex')
| -rw-r--r-- | paper/sections/abstract.tex | 19 |
1 files changed, 10 insertions, 9 deletions
diff --git a/paper/sections/abstract.tex b/paper/sections/abstract.tex index 72a9bf4..3b28765 100644 --- a/paper/sections/abstract.tex +++ b/paper/sections/abstract.tex @@ -1,11 +1,12 @@ -In the Graph Inference problem, one seeks to recover the edges of an unknown -graph from the observations of cascades propagating over this graph. -In this paper, 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 +In the Network Inference problem, one seeks to recover the edges of an unknown +graph from the observations of cascades propagating over this graph. In this +paper, 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. |