Please wait a minute...

Frontiers of Computer Science

Front. Comput. Sci.    2017, Vol. 11 Issue (4) : 568-584     DOI: 10.1007/s11704-016-6108-z
A comparative study of network robustness measures
Jing LIU(), Mingxing ZHOU, Shuai WANG, Penghui LIU
Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education, Xidian University, Xi’an 710071, China
Download: PDF(2369 KB)  
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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     
Corresponding Authors: Jing LIU   
Just Accepted Date: 19 October 2016   Online First Date: 09 June 2017    Issue Date: 26 July 2017
 Cite this article:   
Jing LIU,Mingxing ZHOU,Shuai WANG, et al. A comparative study of network robustness measures[J]. Front. Comput. Sci., 2017, 11(4): 568-584.
E-mail this article
E-mail Alert
Articles by authors
Jing LIU
Mingxing ZHOU
Shuai WANG
Penghui LIU
1 AlbertR, Barabási A L. Statistical mechanics of complex networks. Reviews of Modern Physics, 2002, 74(1): 47
doi: 10.1103/RevModPhys.74.47
2 NewmanM E J. The structure and function of complex networks. SIAM Review, 2003, 45(2): 167–256
doi: 10.1137/S003614450342480
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
doi: 10.1038/30918
5 BarabásiA L, Albert R. Emergence of scaling in random networks. Science, 1999, 286(5439): 509–512
doi: 10.1126/science.286.5439.509
6 AdamicL A, Huberman B A. Power-law distribution of the World Wide Web. Science, 2000, 287(5461): 2115
doi: 10.1126/science.287.5461.2115a
7 GaoJ, Buldyrev S V, HavlinS , StanleyH E. Robustness of a network of networks. Physical Review Letters, 2011, 107(19): 195701
doi: 10.1103/PhysRevLett.107.195701
8 AlbertR, JeongH, BarabásiA L . Error and attack tolerance of complex networks. Nature, 2000, 406(6794): 378–382
doi: 10.1038/35019019
9 PaulG, Sreenivasan S, StanleyH E . Resilience of complex networks to random breakdown. Physical Review E, 2005, 72(5): 056130
doi: 10.1103/PhysRevE.72.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
doi: 10.1103/PhysRevLett.85.5468
11 CohenR, ErezK, Ben-AvrahamD , HavlinS. Resilience of the Internet to random breakdowns. Physical Review Letters, 2000, 85(21): 4626–4628
doi: 10.1103/PhysRevLett.85.4626
12 CohenR, ErezK, Ben-AvrahamD , HavlinS. Breakdown of the Internet under intentional attack. Physical Review Letters, 2001, 86(16): 3682–3685
doi: 10.1103/PhysRevLett.86.3682
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
doi: 10.1140/epjb/e2004-00112-3
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
doi: 10.1073/pnas.1009440108
15 ZengA, LiuW. Enhancing network robustness against malicious attacks. Physical Review E, 2012, 85(6): 066130
doi: 10.1103/PhysRevE.85.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
doi: 10.1007/978-3-319-15916-4_9
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
doi: 10.1109/TSMCA.2011.2116117
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
doi: 10.1209/0295-5075/111/28003
19 LouzadaV H P, DaolioF, HerrmannH J , TomassiniM. Smart rewiring for network robustness. Journal of Complex Networks, 2013, 1(2): 150–159
doi: 10.1093/comnet/cnt010
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
doi: 10.1007/978-3-642-20267-4_18
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
doi: 10.1016/j.physa.2014.05.002
22 HolmeP, KimB J, YoonC N, Han S K. Attack vulnerability of complex networks. Physical Review E, 2002, 65(5): 056109
doi: 10.1103/PhysRevE.65.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
doi: 10.1016/j.physd.2013.03.002
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
doi: 10.1016/j.physa.2015.12.045
26 MaL, LiuJ, DuanB. Evolution of network robustness under continuous topological changes. Physica A: Statistical Mechanics and its Applications, 2016, 451: 623–631
doi: 10.1016/j.physa.2016.01.088
27 TangX, LiuJ, ZhouM. Enhancing network robustness against targeted and random attacks using a memetic algorithm. Europhysics Letters, 2015, 111(3)
doi: 10.1209/0295-5075/111/38005
28 BollobásB. Modern Graph Theory. New York: Springer Science & Business Media, 1998
doi: 10.1007/978-1-4612-0619-4
29 BrandesU. On variants of shortest-path betweenness centrality and their generic computation. Social Networks, 2008, 30(2): 136–145
doi: 10.1016/j.socnet.2007.11.001
30 EstradaE, HighamD J, HatanoN. Communicability betweenness in complex networks. Physica A: Statistical Mechanics and its Applications, 2009, 388(5): 764–774
doi: 10.1016/j.physa.2008.11.011
31 BonacichP. Some unique properties of eigenvector centrality. Social Networks, 2007, 29(4): 555–564
doi: 10.1016/j.socnet.2007.04.002
32 HageP, HararyF. Eccentricity and centrality in networks. Social Networks, 1995, 17(1): 57–63
doi: 10.1016/0378-8733(94)00248-9
33 BorgattiS P. Centrality and network flow. Social Networks, 2005, 27(1): 55–71
doi: 10.1016/j.socnet.2004.11.008
34 FrankH, FrischI T. Analysis and design of survivable network. IEEE Transactions on Communication Technology, 1970, 18(5): 501–519
doi: 10.1109/TCOM.1970.1090419
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
doi: 10.1016/0024-3795(94)90486-3
39 BoeschF, FrischI T. On the smallest disconnecting set in a graph. IEEE Transactions on Circuit Theory, 1968, 15(3): 286–288
doi: 10.1109/TCT.1968.1082832
40 LatoraV, Marchiori M. Efficient behavior of small-world networks. Physical Review Letters, 2001, 87(19): 198701
doi: 10.1103/PhysRevLett.87.198701
[1] FCS-0568-16108-JL_suppl_1 Download
Related articles from Frontiers Journals
[1] Huan LI , . Scale-free network modles with accelerating growth[J]. Front. Comput. Sci., 2009, 3(3): 373-380.
Full text