https://doi.org/10.1140/epjb/e2014-50276-0
Regular Article
Improving robustness of complex networks via the effective graph resistance
1 Faculty of Electrical Engineering,
Mathematics and Computer Science, Delft University of Technology,
2628 CD
Delft, The
Netherlands
2 TNO, Delft, The
Netherlands
a
e-mail: x.wang-2@tudelft.nl
Received:
29
April
2014
Received in final form:
4
August
2014
Published online:
24
September
2014
Improving robustness of complex networks is a challenge in several application domains, such as power grids and water management networks. In such networks, high robustness can be achieved by optimizing graph metrics such as the effective graph resistance, which is the focus of this paper. An important challenge lies in improving the robustness of complex networks under dynamic topological network changes, such as link addition and removal. This paper contributes theoretical and experimental findings about the robustness of complex networks under two scenarios: (i) selecting a link whose addition maximally decreases the effective graph resistance; (ii) protecting a link whose removal maximally increases the effective graph resistance. Upper and lower bounds of the effective graph resistance under these topological changes are derived. Four strategies that select single links for addition or removal, based on topological and spectral metrics, are evaluated on various synthetic and real-world networks. Furthermore, this paper illustrates a novel comparison method by considering the distance between the added or removed links, optimized according to the effective graph resistance and the algebraic connectivity. The optimal links are different in most cases but in close proximity.
Key words: Statistical and Nonlinear Physics
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag, 2014