A comparative study of network robustness measures

Abstract

The robustness is an important functionality of networks because it manifests the ability of networks to resist failures or attacks. Many robustness measures have been proposed from different aspects, which provide us various ways to evaluate the network robustness. However, whether these measures can properly evaluate the network robustness and which aspects of network robustness these measures can evaluate are still open questions. Therefore, in this paper, a thorough introduction over attacks and robustness measures is first given, and then nine widely used robustness measures are comparatively studied. To validate whether a robustness measure can evaluate the network robustness properly, the sensitivity of robustness measures is first studied on both initial and optimized networks. Then, the performance of robustness measures in guiding the optimization process is studied, where both the optimization process and the obtained optimized networks are studied. The experimental results show that, first, the robustness measures are more sensitive to the changes in initial networks than to those in optimized networks; second, an optimized network may not be useful in practical situations because some useful functionalities, such as the shortest path length and communication efficiency, are sacrificed too much to improve the robustness; third, the robustness of networks in terms of closely correlated robustness measures can often be improved together. These results indicate that it is not wise to just apply the optimized networks obtained by optimizing over one certain robustness measure into practical situations. Practical requirements should be considered, and optimizing over two or more suitable robustnessmeasures simultaneously is also a promising way.

Keywords

scale-free network / malicious attack / robustness measure / hill climbing algorithm

References

[1] AlbertR, Barabási A L. Statistical mechanics of complex networks. Reviews of Modern Physics, 2002, 74(1): 47

[2] NewmanM E J. The structure and function of complex networks. SIAM Review, 2003, 45(2): 167–256

[3] DorogovtsevS N, MendesJ F F. Evolution of Networks: from Biological Nets to the Internet and WWW. Oxford: Oxford University Press, 2013

[4] WattsD J, Strogatz S H. Collective dynamics of small-world networks. Nature, 1998, 393(6684): 440–442

[5] BarabásiA L, Albert R. Emergence of scaling in random networks. Science, 1999, 286(5439): 509–512

[6] AdamicL A, Huberman B A. Power-law distribution of the World Wide Web. Science, 2000, 287(5461): 2115

[7] GaoJ, Buldyrev S V, HavlinS , StanleyH E. Robustness of a network of networks. Physical Review Letters, 2011, 107(19): 195701

[8] AlbertR, JeongH, BarabásiA L . Error and attack tolerance of complex networks. Nature, 2000, 406(6794): 378–382

[9] PaulG, Sreenivasan S, StanleyH E . Resilience of complex networks to random breakdown. Physical Review E, 2005, 72(5): 056130

[10] CallawayD S, NewmanM E J, StrogatzS H , WattsD J. Network robustness and fragility: percolation on random graphs. Physical Review Letters, 2000, 85(25): 5468–5471

[11] CohenR, ErezK, Ben-AvrahamD , HavlinS. Resilience of the Internet to random breakdowns. Physical Review Letters, 2000, 85(21): 4626–4628

[12] CohenR, ErezK, Ben-AvrahamD , HavlinS. Breakdown of the Internet under intentional attack. Physical Review Letters, 2001, 86(16): 3682–3685

[13] PaulG, Tanizawa T, HavlinS , StanleyH E. Optimization of robustness of complex networks. The European Physical Journal B Condensed Matter and Complex Systems, 2004, 38(2): 187–191

[14] SchneiderC M, Moreira A A, AndradeJ S , HavlinS, Herrmann H J. Mitigation of malicious attacks on networks. Proceedings of National Academy of Sciences of the United States of America, 2011, 108(10): 3838–3841

[15] ZengA, LiuW. Enhancing network robustness against malicious attacks. Physical Review E, 2012, 85(6): 066130

[16] LouzadaV H P, DaolioF, HerrmannH J , TomassiniM. Generating robust and efficient networks under targeted attacks. In: Król D, Fay D, Gabrýs B, eds. Propagation Phenomena in Real World Networks. Intelligent System Reference Library, Vol 85. Springer International Publishing, 2015, 215–224

[17] WuJ, Barahona M, TanY J , DengH Z. Spectral measure of structural robustness in complex networks. IEEE Transactions on Systems Man and Cybernetics Part A: Systems and Humans, 2011, 41(6): 1244–1252

[18] MaL, LiuJ, DuanB, Zhou M. A theoretical estimation for the optimal network robustness measure R against malicious node attacks. Europhysics Letters, 2015, 111: 28003

[19] LouzadaV H P, DaolioF, HerrmannH J , TomassiniM. Smart rewiring for network robustness. Journal of Complex Networks, 2013, 1(2): 150–159

[20] BuesserP, DaolioF, TomassiniM. Optimizing the robustness of scalefree networks with simulated annealing. In: Proceedings of International Conference on Adaptive and Natural Computing Algorithms. 2011, 167–176

[21] ZhouM, LiuJ. A memetic algorithm for enhancing the robustness of scale-free networks against malicious attacks. Physica A: Statistical Mechanics and its Applications, 2014, 410: 131–143

[22] HolmeP, KimB J, YoonC N, Han S K. Attack vulnerability of complex networks. Physical Review E, 2002, 65(5): 056109

[23] QinJ,WuH, TongX, Zheng B. A quantitative method for determining the robustness of complex networks. Physica D: Nonlinear Phenomena, 2013, 253: 85–90

[24] ZhouM, LiuJ. A two-phase multi-objective evolutionary algorithm for enhancing the robustness of scale-free networks against multiple malicious attacks. IEEE Transactions on Cybernetics, 2017, 47(2): 539–552

[25] DuanB, LiuJ, ZhouM, Ma L. A comparative analysis of network robustness against different link attacks. Physica A: Statistical Mechanics and its Applications, 2016, 448: 144–153

[26] MaL, LiuJ, DuanB. Evolution of network robustness under continuous topological changes. Physica A: Statistical Mechanics and its Applications, 2016, 451: 623–631

[27] TangX, LiuJ, ZhouM. Enhancing network robustness against targeted and random attacks using a memetic algorithm. Europhysics Letters, 2015, 111(3)

[28] BollobásB. Modern Graph Theory. New York: Springer Science & Business Media, 1998

[29] BrandesU. On variants of shortest-path betweenness centrality and their generic computation. Social Networks, 2008, 30(2): 136–145

[30] EstradaE, HighamD J, HatanoN. Communicability betweenness in complex networks. Physica A: Statistical Mechanics and its Applications, 2009, 388(5): 764–774

[31] BonacichP. Some unique properties of eigenvector centrality. Social Networks, 2007, 29(4): 555–564

[32] HageP, HararyF. Eccentricity and centrality in networks. Social Networks, 1995, 17(1): 57–63

[33] BorgattiS P. Centrality and network flow. Social Networks, 2005, 27(1): 55–71

[34] FrankH, FrischI T. Analysis and design of survivable network. IEEE Transactions on Communication Technology, 1970, 18(5): 501–519

[35] BauerD, BoeschF, SuffelC, Tindell R. Connectivity extremal problems and the design of reliable probabilistic networks. The Theory and Application of Graphs, 1981, 89–98

[36] HararyF. Conditional connectivity. Networks, 2983, 13(3): 346–357

[37] FiedlerM. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 1973, 23(98): 298–305

[38] MerrisR. Laplacian matrices of graphs: a survey. Linear Algebra Applications, 1994, 197: 143–176

[39] BoeschF, FrischI T. On the smallest disconnecting set in a graph. IEEE Transactions on Circuit Theory, 1968, 15(3): 286–288

[40] LatoraV, Marchiori M. Efficient behavior of small-world networks. Physical Review Letters, 2001, 87(19): 198701

[41] ZhouQ, BialekJ W. Approximate model of European interconnected system as a benchmark system to study effects of cross-border trades. IEEE Transactions on Power Systems, 2005, 20(2): 782–788

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg