Coexistence of phases and the observability of random graphs

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.

14 pages, 5 figures and 1 table

References in corpus (11)

• Power-law distributions in empirical data
• Uncovering the overlapping community structure of complex networks in nature and society
• Self-similarity of complex networks and hidden metric spaces
• Control centrality and hierarchical structure in complex networks
• Emergence of bimodality in controlling complex networks
• Controllability transition and nonlocality in network control
• Rescuing ecosystems from extinction cascades through compensatory perturbations
• Deciphering the global organization of clustering in real complex networks
• Network Observability Transitions
• Percolation on random networks with arbitrary k-core structure
• Observability transitions in correlated networks

Cited by in corpus (3)

• Percolation on complex networks: Theory and application
• General and exact approach to percolation on random graphs
• Observability transitions in clustered networks