Optimizing network robustness by edge rewiring: a general framework. (English) Zbl 1409.05190

Summary: 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 EdgeRewire, which optimizes a specific measure of interest directly. Notably, 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 EdgeRewire produces graphs with both (i) higher robustness, and (ii) higher attack-tolerance over several state-of-the-art methods.


05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
05C90 Applications of graph theory
68R10 Graph theory (including graph drawing) in computer science


EdgeRewire; OddBall
Full Text: DOI


[1] Akoglu L, McGlohon M, Faloutsos C (2010) Oddball: spotting anomalies in weighted graphs. In: Proceedings of the 14th Pacific-Asia conference on advances in knowledge discovery and data mining—volume Part II, PAKDD’10, pp 410-421
[2] Albert, R.; Jeong, H.; Barabasi, A-L, Error and attack tolerance of complex networks, Nature, 406, 378-382, (2000)
[3] Baras J, Hovareshti P (2009) Efficient and robust communication topologies for distributed decision making in networked systems. In: Proceedings of the 48th IEEE conference on decision and control, held jointly with the 2009 28th Chinese control conference, CDC/CCC’09, pp 3751-3756
[4] Beygelzimer, A.; Grinstein, G.; Linsker, R.; Rish, I., Improving network robustness by edge modification, Phys A Stat Mech Appl, 357, 593-612, (2005)
[5] Brouwer AE, Haemers WH (2012) Spectra of graphs. Springer, New York · Zbl 1231.05001
[6] Buekenhout F, Parker M (1998) The number of nets of the regular convex polytopes in dimension \(\le \)4. Discret Math 186(1-3):69-94 · Zbl 0956.52014
[7] Chakrabarti, D.; Wang, Y.; Wang, C.; Leskovec, J.; Faloutsos, C., Epidemic thresholds in real networks, ACM Trans Inf Syst Secur, 10, 1:1-1:26, (2008)
[8] Chan H, Akoglu L, Tong H (2014) Make it or break it: manipulating robustness in large networks. In: Proceedings of the 2014 SIAM international conference on data mining, SDM’14, pp 325-333
[9] Chan H, Han S, Akoglu L (2015) Where graph topology matters: the robust subgraph problem. In: Proceedings of the 2015 SIAM international conference on data mining, SDM’15, pp 10-18
[10] Chandra AK, Raghavan P, Ruzzo WL, Smolensky R (1989) The electrical resistance of a graph captures its commute and cover times. In: Proceedings of the twenty-first annual ACM symposium on theory of computing, STOC ’89, pp 574-586
[11] Cvetković DM, Doob M, Sachs H (1980) Spectra of graphs: theory and application. Academic Press, New York · Zbl 0458.05042
[12] Costa, L. da F.; Rodrigues, F A; Travieso, G.; Boas, P R V, Characterization of complex networks: a survey of measurements, Adv Phys, 56, 167-242, (2007)
[13] Ellens W, Kooij RE (2013) Graph measures and network robustness. CoRR 1-13. arxiv:1311.5064
[14] Ellens, W.; Spieksma, F.; Mieghem, P.; Jamakovic, A.; Kooij, R., Effective graph resistance, Linear Algebra Appl, 435, 2491-2506, (2011) · Zbl 1222.05155
[15] Estrada, E., Network robustness to targeted attacks. The interplay of expansibility and degree distribution, Phys J B Complex Syst, 52, 563-574, (2006) · Zbl 1189.68018
[16] Estrada, E.; Hatano, N.; Benzi, M., The physics of communicability in complex networks, Phys Rep, 514, 89-119, (2012)
[17] Faloutsos, M.; Faloutsos, P.; Faloutsos, C., On power-law relationships of the internet topology, SIGCOMM Comput Commun Rev, 29, 251-262, (1999) · Zbl 0889.68050
[18] Fiedler, M., Algebraic connectivity of graphs, Czechoslov Math J, 23, 298-305, (1973) · Zbl 0265.05119
[19] Ghosh, A.; Boyd, S.; Saberi, A., Minimizing effective resistance of a graph, SIAM Rev, 50, 37-66, (2008) · Zbl 1134.05057
[20] Holme, P.; Kim, BJ; Yoon, CN; Han, SK, Attack vulnerability of complex networks, Phys Rev E, 65, 056109, (2002)
[21] Jamakovic A, Van Mieghem P (2008) On the robustness of complex networks by using the algebraic connectivity. In: Proceedings of the 7th international IFIP-TC6 networking conference on AdHoc and sensor networks, wireless networks, next generation internet, NETWORKING’08, pp 183-194
[22] Klein, DJ; Randić, M., Resistance distance, Math Chem, 12, 81-95, (1993)
[23] Latora, V.; Marchiori, M., A measure of centrality based on the network efficiency, New J Phys, 9, 188, (2007)
[24] Le LT, Eliassi-Rad T, Tong H (2015) Met: a fast algorithm for minimizing propagation in large graphs with small eigen-gaps. In: Proceedings of the 2015 SIAM international conference on data mining, SDM’15, pp 694-702
[25] Louzada, VHP; Daolio, F.; Herrmann, HJ; Tomassini, M., Smart rewiring for network robustness, J Complex Netw, 1, 150-159, (2013)
[26] Malliaros FD, Megalooikonomou V, Faloutsos C (2012) Fast robustness estimation in large social graphs: communities and anomaly detection. In: Proceedings of the 2012 SIAM international conference on data mining, SDM’12, pp 942-953
[27] Matisziw, TC; Murray, AT, Modeling s-t path availability to support disaster vulnerability assessment of network infrastructure, Comput Oper Res, 36, 16-26, (2009) · Zbl 1163.90441
[28] Mosk-Aoyama, D., Maximum algebraic connectivity augmentation is np-hard, Oper Res Lett, 36, 677-679, (2008) · Zbl 1152.05343
[29] Newman, MEJ, Mixing patterns in networks, Phys Rev E, 67, 026126, (2003)
[30] Saha S, Adiga A, Prakash BA, Vullikanti AKS (2015) Approximation algorithms for reducing the spectral radius to control epidemic spread. In: Proceedings of the 2015 SIAM international conference on data mining, SDM’15, pp 568-576
[31] Scellato, S.; Leontiadis, I.; Mascolo, C.; Basu, P.; Zafer, M., Evaluating temporal robustness of mobile networks, IEEE Trans Mob Comput, 12, 105-117, (2013)
[32] Schneider, CM; Moreira, AA; Andrade, JS; Havlin, S.; Herrmann, HJ, Mitigation of malicious attacks on networks, Proc Natl Acad Sci, 108, 3838-3841, (2011)
[33] Stewart GW, Sun J-G (1990) Matrix perturbation theory. Academic Press, New York · Zbl 0706.65013
[34] Sun, F.; Shayman, MA, On pairwise connectivity of wireless multihop networks, Int J Netw Secur, 2, 37-49, (2007)
[35] Sydney, A.; Scoglio, C.; Gruenbacher, D., Optimizing algebraic connectivity by edge rewiring, Appl Math Comput, 219, 5465-5479, (2013) · Zbl 1280.05072
[36] Tong H, Prakash BA, Eliassi-Rad T, Faloutsos M, Faloutsos C (2012) Gelling, and melting, large graphs by edge manipulation. In: Proceedings of the 21st ACM international conference on information and knowledge management, CIKM ’12, pp 245-254
[37] Tong H, Prakash BA, Tsourakakis C, Eliassi-Rad T, Faloutsos C, Chau DH (2010) On the vulnerability of large graphs. In: Proceedings of the 2010 IEEE international conference on data mining, ICDM ’10, pp 1091-1096
[38] Tsourakakis CE (2008) Fast counting of triangles in large real networks without counting: algorithms and laws. In: Proceedings of the 2008 eighth IEEE international conference on data mining, ICDM ’08, pp 608-617
[39] Mieghem, P.; Stevanović, D.; Kuipers, F.; Li, C.; Bovenkamp, R.; Liu, D.; Wang, H., Decreasing the spectral radius of a graph by link removals, Phys Rev E, 84, 016101, (2011)
[40] Mieghem, P.; Wang, H.; Ge, X.; Tang, S.; Kuipers, FA, Influence of assortativity and degree-preserving rewiring on the spectra of networks, Eur Phys J B, 76, 643-652, (2010) · Zbl 1202.05131
[41] Wang H, Van Mieghem P (2008) Algebraic connectivity optimization via link addition. In: Proceedings of the 3rd international conference on bio-inspired models of network, information and computing systems, BIONETICS ’08, pp 22:1-22:8
[42] Wu, J.; Mauricio, B.; Tan, Y-J; Deng, H-Z, Natural connectivity of complex networks, Chin Phys Lett, 27, 078902, (2010)
[43] Zeng, A.; Liu, W., Enhancing network robustness against malicious attacks, Phys Rev E, 85, 066130, (2012)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.