blob: ad5b89382680e4d1883bd6353465eda3f100ca31 (
plain)
1
2
3
4
5
6
7
8
9
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 prove an almost matching lower bound of
$\Omega(s\log\frac{m}{s})$.
|
