Source-linked AI summary
Locating the Source of Diffusion in Large-Scale Networks
Pedro C. Pinto, Patrick Thiran, Martin Vetterli
TL;DR
The paper asks whether diffusion sources can be localized in large networks when only a small fraction of nodes is observed. It develops estimators for trees and arbitrary graphs, finding that sparse observation can support accurate, computationally feasible localization, while graph knowledge and observer placement remain important limitations.
Problem
The paper addresses source localization under the practical constraint that only a small fraction of network nodes can be observed.
Method
The paper uses maximum-probability localization from observer measurements, with an optimal tree estimator and a BFS-tree approximation for arbitrary graphs.
Results
The tree strategy has complexity O(N), the general-graph strategy has complexity O(N^3), and scale-free networks can achieve Ploc = 90% with as few as 4% observers in some cases.
Takeaways & Limitations
Sparse observer deployment may provide an effective alternative to monitoring every node, making source localization feasible in large networks.
Takeaways & Limitations
General-graph localization assumes the diffusion tree is a breadth-first search tree, and performance depends strongly on the underlying graph and observer placement.
Abstract
from arXiv · showhide
How can we localize the source of diffusion in a complex network? Due to the tremendous size of many real networks--such as the Internet or the human social graph--it is usually infeasible to observe the state of all nodes in a network. We show that it is fundamentally possible to estimate the location of the source from measurements collected by sparsely-placed observers. We present a strategy that is optimal for arbitrary trees, achieving maximum probability of correct localization. We describe efficient implementations with complexity O(N^α), where α=1 for arbitrary trees, and α=3 for arbitrary graphs. In the context of several case studies, we determine how localization accuracy is affected by various system parameters, including the structure of the network, the density of observers, and the number of observed cascades.