Fault Tolerance of Random Graphs with respect to Connectivity: Mean-field Approximation for Semi-dense Random Graphs
arXiv:1712.07807 · doi:10.1103/PhysRevE.99.050304
Abstract
The fault tolerance of random graphs with unbounded degrees with respect to connectivity is investigated, which relates to the reliability of wireless sensor networks with unreliable relay nodes. The model evaluates the network breakdown probability that a graph is disconnected after stochastic node removal. To establish a mean-field approximation for the model, we propose the cavity method for finite systems. The analysis enables us to obtain an approximation formula for random graphs with any number of nodes and an arbitrary degree distribution. In addition, its asymptotic analysis reveals that the phase transition occurs in semi-dense random graphs whose average degree grows logarithmically. These results, which are supported by numerical simulations, coincide with the mathematical results, indicating successful predictions by mean-field approximation for unbounded but not dense random graphs.
arXiv comment5 pages, 3 figures
References in corpus (24)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- Error and attack tolerance of complex networks
- Assortative mixing in networks
- Finding community structure in networks using the eigenvectors of matrices
- Random graphs with arbitrary degree distributions and their applications
- Network robustness and fragility: Percolation on random graphs
- Resilience of the Internet to random breakdowns
- Critical phenomena in complex networks
- Breakdown of the Internet under intentional attack
- Structural Vulnerability of the North American Power Grid
- The Bethe lattice spin glass revisited
- Phase transition in the detection of modules in sparse networks
- Percolation on sparse networks
- Resilience to damage of graphs with degree correlations
- Interdependent networks with correlated degrees of mutually dependent nodes
- Ising models on locally tree-like graphs
- The number of guards needed by a museum: A phase transition in vertex covering of random graphs
- Optimization of Robustness of Complex Networks
- Random geometric graphs with general connection functions
- Cavity-based robustness analysis of interdependent networks: Influences of intranetwork and internetwork degree-degree correlations
- Nonbacktracking expansion of finite graphs
- Cavity analysis on the robustness of random networks against targeted attacks: Influences of degree-degree correlations
- Community Detection and Stochastic Block Models