Coexistence of phases and the observability of random graphs
arXiv:1309.7983 · doi:10.1103/PhysRevE.89.022801
Abstract
In a recent Letter, Yang et al. [Phys. Rev. Lett. 109, 258701 (2012)] introduced the concept of observability transitions: the percolation-like emergence of a macroscopic observable component in graphs in which the state of a fraction of the nodes, and of their first neighbors, is monitored. We show how their concept of depth-L percolation---where the state of nodes up to a distance L of monitored nodes is known---can be mapped unto multitype random graphs, and use this mapping to exactly solve the observability problem for arbitrary L. We then demonstrate a non-trivial coexistence of an observable and of a non-observable extensive component. This coexistence suggests that monitoring a macroscopic portion of a graph does not prevent a macroscopic event to occur unbeknown to the observer. We also show that real complex systems behave quite differently with regard to observability depending on whether they are geographically-constrained or not.
arXiv comment14 pages, 5 figures and 1 table
References in corpus (25)
- Emergence of scaling in random networks
- Power-law distributions in empirical data
- Power laws, Pareto distributions and Zipf's law
- Uncovering the overlapping community structure of complex networks in nature and society
- Random graphs with arbitrary degree distributions and their applications
- The spread of epidemic disease on networks
- Network robustness and fragility: Percolation on random graphs
- Self-similar community structure in organisations
- Controlling edge dynamics in complex networks
- Controlling complex networks: How much energy is needed?
- Self-similarity of complex networks and hidden metric spaces
- Control centrality and hierarchical structure in complex networks
- Nodal dynamics, not degree distributions, determine the structural controllability of complex networks
- Emergence of bimodality in controlling complex networks
- Effect of correlations on network controllability
- Controllability transition and nonlocality in network control
- Rescuing ecosystems from extinction cascades through compensatory perturbations
- Heterogeneous Bond Percolation on Multitype Networks with an Application to Epidemic Dynamics
- Deciphering the global organization of clustering in real complex networks
- Network Observability Transitions
- Structural preferential attachment: Network organization beyond the link
- Bond percolation on a class of correlated and clustered random graphs
- Percolation on random networks with arbitrary k-core structure
- Propagation on networks: an exact alternative perspective
- Observability transitions in correlated networks