Robustness of random graphs based on graph spectra
From MaRDI portal
Abstract: Recently, it has been proposed that the natural connectivity can be used to efficiently characterise the robustness of complex networks. Natural connectivity quantifies the redundancy of alternative routes in a network by evaluating the weighted number of closed walks of all lengths and can be regarded as the average eigenvalue obtained from the graph spectrum. In this article, we explore the natural connectivity of random graphs both analytically and numerically and show that it increases linearly with the average degree. By comparing with regular ring lattices and random regular graphs, we show that random graphs are more robust than random regular graphs; however, the relationship between random graphs and regular ring lattices depends on the average degree and graph size. We derive the critical graph size as a function of the average degree, which can be predicted by our analytical results. When the graph size is less than the critical value, random graphs are more robust than regular ring lattices, whereas regular ring lattices are more robust than random graphs when the graph size is greater than the critical value.
Recommendations
Cites work
- scientific article; zbMATH DE number 3863589 (Why is no real title available?)
- scientific article; zbMATH DE number 861347 (Why is no real title available?)
- scientific article; zbMATH DE number 2194270 (Why is no real title available?)
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- Characteristic vectors of bordered matrices with infinite dimensions
- Collective dynamics of `small-world' networks
- Conditional connectivity
- Congruent Graphs and the Connectivity of Graphs
- Eigenvalue spectra of complex networks
- Eigenvalues and expanders
- Estimating the Estrada index
- Expander graphs and their applications
- Explosive percolation in random networks
- Fault diameter of interconnection networks
- Generating Random Regular Graphs Quickly
- Generating random regular graphs
- Graph spectra for complex networks
- Isoperimetric numbers of graphs
- Network robustness to targeted attacks. The interplay of expansibility and degree distribution
- On a class of posets and the corresponding comparability graphs
- On computing a conditional edge-connectivity of a graph
- Perturbation results for the Estrada index in weighted networks
- Robustness of regular ring lattices based on natural connectivity
- Spectra of random graphs with given expected degrees
- Statistical mechanics of complex networks
- TOPOLOGICAL VULNERABILITY OF THE EUROPEAN POWER GRID UNDER ERRORS AND ATTACKS
- The Largest Eigenvalue of Sparse Random Graphs
- The Structure and Function of Complex Networks
- Tough graphs and Hamiltonian circuits.
- Vulnerability of complex networks under intentional attack with incomplete information
Cited in
(15)- The natural connectivity of colored random graphs
- Updating and downdating techniques for optimizing network communicability
- Robustness measurement of multiplex networks based on graph spectrum
- A new method optimizing the subgraph centrality of large networks
- Tabu search enhances network robustness under targeted attacks
- Scaling of weighted spectral distribution in deterministic scale-free networks
- Reduced synchronizability of dynamical scale-free networks with onion-like topologies
- The robustness of LWPP and WPP, with an application to graph reconstruction
- Random lifts of graphs: network robustness based on the Estrada index
- About some robustness and complexity properties of G-graphs networks
- scientific article; zbMATH DE number 7055493 (Why is no real title available?)
- Robustness of regular ring lattices based on natural connectivity
- Edge modification criteria for enhancing the communicability of digraphs
- Uncertain random spectra: a new metric for assessing the survivability of mobile wireless sensor networks
- Bounding robustness in complex networks under topological changes through majorization techniques
This page was built for publication: Robustness of random graphs based on graph spectra
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2944617)
