Inferring Graphs from Cascades
2015pp. 625–626
Citations Over TimeTop 21% of 2015 papers
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 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 validate our approach empirically on synthetic graphs.
Related Papers
- → Evaluating the Inference Mechanism of Adaptive Learning Systems(2003)37 cited
- → Automatic Inference of Bounds on Resource Consumption(2013)2 cited
- → Scalable RDFS Reasoning Using the Graph Structure of In-Memory based Parallel Computing(2015)
- A New Accelerating Iterative Algorithm for Constructing Cascade No Sequences(2006)
- A Fine-Grained Inference Control Mechanism of XML(2006)