Home // PESARO 2012, The Second International Conference on Performance, Safety and Robustness in Complex Systems and Applications // View article

Robustness of Random Graphs Based on Natural Connectivity

Authors:
Jun Wu
Yuejin Tan
Hongzhong Deng
Mauricio Barahona

Keywords: natural connectivity; robustness; complex networks; random graphs; regular graphs.

Abstract:
Recently, it has been proposed that the natural connectivity can be used to efficiently characterize 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 paper, 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.

Pages: 14 to 20

Copyright: Copyright (c) IARIA, 2012

Publication date: April 29, 2012

Published in: conference

ISSN: 2308-3700

ISBN: 978-1-61208-198-4

Location: Chamonix, France

Dates: from April 29, 2012 to May 4, 2012