EdgeRewire
swMATH ID:  40656 
Software Authors:  Chan, Hau; Akoglu, Leman 
Description:  Optimizing network robustness by edge rewiring: a general framework. Spectral measures have long been used to quantify the robustness of realworld graphs. For example, spectral radius (or the principal eigenvalue) is related to the effective spreading rates of dynamic processes (e.g., rumor, disease, information propagation) on graphs. Algebraic connectivity (or the Fiedler value), which is a lower bound on the node and edge connectivity of a graph, captures the “partitionability” of a graph into disjoint components. In this work we address the problem of modifying a given graph’s structure under a given budget so as to maximally improve its robustness, as quantified by spectral measures. We focus on modifications based on degreepreserving edge rewiring, such that the expected load (e.g., airport flight capacity) or physical/hardware requirement (e.g., count of ISP router traffic switches) of nodes remain unchanged. Different from a vast literature of measureindependent heuristic approaches, we propose an algorithm, called extsc{EdgeRewire}, which optimizes a specific measure of interest directly. Notably, extsc{EdgeRewire} is general to accommodate six different spectral measures. Experiments on realworld datasets from three different domains (Internet ASlevel, P2P, and airport flights graphs) show the effectiveness of our approach, where extsc{EdgeRewire} produces graphs with both (i) higher robustness, and (ii) higher attacktolerance over several stateoftheart methods. 
Homepage:  https://link.springer.com/article/10.1007%2Fs1061801504475 
Keywords:  graph robustness; edge rewiring; robustnesss measures; graph spectrum; optimization algorithms; attack tolerance 
Related Software:  KONECT; NetComm; Pajek; NetworKit; igraph; SNAP; NetworkX; OddBall; AS 136; Silhouettes 
Cited in:  7 Publications 
Standard Articles
1 Publication describing the Software, including 1 Publication in zbMATH  Year 

Optimizing network robustness by edge rewiring: a general framework. Zbl 1409.05190 Chan, Hau; Akoglu, Leman 
2016

all
top 5
Cited by 17 Authors
all
top 5
Cited in 6 Serials
all
top 5