Observability transition in real networks
arXiv:1607.07124 · doi:10.1103/PhysRevE.94.030301
Abstract
We consider the observability model in networks with arbitrary topologies. We introduce a system of coupled nonlinear equations, valid under the locally tree-like ansatz, to describe the size of the largest observable cluster as a function of the fraction of directly observable nodes present in the network. We perform a systematic analysis on 95 real-world graphs and compare our theoretical predictions with numerical simulations of the observability model. Our method provides almost perfect predictions in the majority of the cases, even for networks with very large values of the clustering coefficient. Potential applications of our theory include the development of efficient and scalable algorithms for real-time surveillance of social networks, and monitoring of technological networks.
5 pages, 3 figures + appendix
References in corpus (13)
- The structure of scientific collaboration networks
- Influence maximization in complex networks through optimal percolation
- Spectral redemption: clustering sparse networks
- Efficient Monte Carlo algorithm and high-precision results for percolation
- Percolation on sparse networks
- Percolation in real interdependent networks
- The unreasonable effectiveness of tree-based theory for networks with clustering
- Predicting percolation thresholds in networks
- Breaking of the site-bond percolation universality in networks
- Tight lower bound for percolation threshold on a quasi-regular graph
- Network Observability Transitions
- Beyond the locally tree-like approximation for percolation on real networks
- Observability transitions in correlated networks