Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2017, Vol. 11 Issue (4) : 568-584    https://doi.org/10.1007/s11704-016-6108-z
NSFC EXCELLENT YOUNG SCHOLAR FORUM
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
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     
Corresponding Author(s): 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.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-016-6108-z
https://academic.hep.com.cn/fcs/EN/Y2017/V11/I4/568
1 AlbertR, Barabási A L. Statistical mechanics of complex networks. Reviews of Modern Physics, 2002, 74(1): 47
https://doi.org/10.1103/RevModPhys.74.47
2 NewmanM E J. The structure and function of complex networks. SIAM Review, 2003, 45(2): 167–256
https://doi.org/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
https://doi.org/10.1038/30918
5 BarabásiA L, Albert R. Emergence of scaling in random networks. Science, 1999, 286(5439): 509–512
https://doi.org/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
https://doi.org/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
https://doi.org/10.1103/PhysRevLett.107.195701
8 AlbertR, JeongH, BarabásiA L . Error and attack tolerance of complex networks. Nature, 2000, 406(6794): 378–382
https://doi.org/10.1038/35019019
9 PaulG, Sreenivasan S, StanleyH E . Resilience of complex networks to random breakdown. Physical Review E, 2005, 72(5): 056130
https://doi.org/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
https://doi.org/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
https://doi.org/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
https://doi.org/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
https://doi.org/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
https://doi.org/10.1073/pnas.1009440108
15 ZengA, LiuW. Enhancing network robustness against malicious attacks. Physical Review E, 2012, 85(6): 066130
https://doi.org/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
https://doi.org/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
https://doi.org/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
https://doi.org/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
https://doi.org/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
https://doi.org/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
https://doi.org/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
https://doi.org/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
https://doi.org/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
https://doi.org/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
https://doi.org/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)
https://doi.org/10.1209/0295-5075/111/38005
28 BollobásB. Modern Graph Theory. New York: Springer Science & Business Media, 1998
https://doi.org/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
https://doi.org/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
https://doi.org/10.1016/j.physa.2008.11.011
31 BonacichP. Some unique properties of eigenvector centrality. Social Networks, 2007, 29(4): 555–564
https://doi.org/10.1016/j.socnet.2007.04.002
32 HageP, HararyF. Eccentricity and centrality in networks. Social Networks, 1995, 17(1): 57–63
https://doi.org/10.1016/0378-8733(94)00248-9
33 BorgattiS P. Centrality and network flow. Social Networks, 2005, 27(1): 55–71
https://doi.org/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
https://doi.org/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
https://doi.org/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
https://doi.org/10.1109/TCT.1968.1082832
40 LatoraV, Marchiori M. Efficient behavior of small-world networks. Physical Review Letters, 2001, 87(19): 198701
https://doi.org/10.1103/PhysRevLett.87.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
https://doi.org/10.1109/TPWRS.2005.846178
[1] FCS-0568-16108-JL_suppl_1 Download
[1] Huan LI , . Scale-free network modles with accelerating growth[J]. Front. Comput. Sci., 2009, 3(3): 373-380.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed