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 real-world 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 degree-preserving 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 measure-independent 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 real-world datasets from three different domains (Internet AS-level, P2P, and airport flights graphs) show the effectiveness of our approach, where extsc{EdgeRewire} produces graphs with both (i) higher robustness, and (ii) higher attack-tolerance over several state-of-the-art methods. Homepage: https://link.springer.com/article/10.1007%2Fs10618-015-0447-5 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.05190Chan, Hau; Akoglu, Leman 2016 all top 5 Cited by 17 Authors 1 Akoglu, Leman 1 Alalwan, Najlaa 1 Arenas, Alex 1 Babaei, Amin 1 Chan, Hau 1 Estrada, Ernesto 1 Gunasekara, R. Chulaka 1 Lozano, Manuel 1 Mehrotra, Kishan G. 1 Mohan, Chilukuri Krishna 1 Moudi, Mehrnaz 1 Ramos, Guilherme 1 Safaei, Farshad 1 Silvestre, Carlos J. 1 Silvestre, Daniel A. M. M. 1 Trujillo, Humberto M. 1 Yeganloo, H. all top 5 Cited in 6 Serials 1 Applied Mathematics and Computation 1 Mathematics and Computers in Simulation 1 Systems & Control Letters 1 Computers & Operations Research 1 Data Mining and Knowledge Discovery 1 Journal of Systems Science and Complexity all top 5 Cited in 7 Fields 3 Combinatorics (05-XX) 3 Operations research, mathematical programming (90-XX) 2 Systems theory; control (93-XX) 1 Statistics (62-XX) 1 Numerical analysis (65-XX) 1 Computer science (68-XX) 1 Information and communication theory, circuits (94-XX) Citations by Year