Vulnerability of complex networks. (English) Zbl 1221.91043

Summary: We consider normalized average edge betweenness of a network as a metric of network vulnerability. We suggest that normalized average edge betweenness together with is relative difference when certain number of nodes and/or edges are removed from the network is a measure of network vulnerability, called vulnerability index. Vulnerability index is calculated for four synthetic networks: Erdős–Rényi (ER) random networks, Barabási–Albert (BA) model of scale-free networks, Watts–Strogatz (WS) model of small-world networks, and geometric random networks. Real-world networks for which vulnerability index is calculated include: two human brain networks, three urban networks, one collaboration network, and two power grid networks. We find that WS model of small-world networks and biological networks (human brain networks) are the most robust networks among all networks studied in the paper.


91D30 Social networks; opinion dynamics
05C82 Small world graphs, complex networks (graph-theoretic aspects)


Full Text: DOI Link


[1] Albert, R.; Barabási, A.L., Statistical mechanics of complex networks, Rev mod phys, 74, 1, 47-97, (2002) · Zbl 1205.82086
[2] Albert, R.; Jeong, H.; Barabási, A.-L., The diameter of the world wide web, Nature (London), 4-6, 378, (1999)
[3] Watts, D.J., A simple model of global cascades on random networks, Proc natl acad sci USA, 99, 9, 5766-5771, (2002) · Zbl 1022.90001
[4] Holme, P.; Kim, B.J.; Yoon, C.N.; Han, S.K., Attack vulnerability of complex networks, Phys rev E, 65, 5, 056109, (2002)
[5] Albert, R.; Albert, I.; Nakarado, G.L., Structural vulnerability of the north American power grid, Phys rev E, 69, 025103(R), (2004)
[6] Huang, L.; Lai, Y.-C.; Park, K.; Zhang, J., Percolation and blind spots in complex networks, Phys rev E, 73, 066131, (2006)
[7] Motter, A.E.; Lai, Y.-C., Cascade-based attacks on complex networks, Phys rev E, 66, 065102(R), (2002)
[8] Motter, A.E., Cascade control and defense in complex networks, Phys rev lett, 93, 098701, (2004)
[9] Crucitti, P.; Latora, V.; Marchiori, M., Model for cascading failures in complex networks, Phys rev E, 69, 045104(R), (2004)
[10] Huang, L.; Yang, L.; Yang, K., Geographical effects on cascading breakdowns of scale-free networks, Phys rev E, 73, 036102, (2006)
[11] Latora, V.; Marchiori, M., Vulnerability and protection of critical infrastructures, Phys rev E, 71, 015103(R), (2004)
[12] Gol’dshtein V, Koganov GA, Surdutovich GI. Vulnerability and hierarchy of complex networks. cond-mat/0409298; 2004.
[13] Boccaletti, S.; Buldu, J.; Criado, R.; Flores, J.; Latora, V.; Pello, J., Multi-scale vulnerability in complex networks, Chaos, 17, 043110, (2007) · Zbl 1163.37312
[14] Brin, S.; Page, L., The anatomy of a large-scale hypertextual web search engine, Comput netw ISDN syst, 30, 1-7, 107-117, (1998)
[15] Watts, D.J.; Strogatz, S.H., Collective dynamics of ‘small-world’ networks, Nature, 393, 440-442, (1998) · Zbl 1368.05139
[16] Penrose, M., Random geometric graphs (Oxford studies in probability), (2003), Oxford University Press USA
[17] Huang, L.; Lai, Y.-C.; Park, K.; Zhang, J.; Hu, Z., Critical behavior of blind spots in sensor networks, Chaos, 17, 023132, (2007) · Zbl 1159.37355
[18] Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 509-512, (1999) · Zbl 1226.05223
[19] Fronczak, A.; Fronczak, P.; Holyst, J.A., Average path length in random networks, Phys rev E, 70, 056110, (2004)
[20] Hagmann, P.; Kurant, M.; Gigandet, X.; Thiran, P.; Wedeen, V.J.; Meuli, R., Mapping human whole-brain structural networks with diffusion mri, Plos one, 2, 7, e597+, (2007)
[21] Batagelj, V.; Mrvar, A., Pajek – program for large network analysis, Connections, 21, 2, 47-57, (1998)
[22] Bao, Z.J.; Cao, Y.J.; Ding, L.J.; Wang, G.Z., Comparison of cascading failures in small-world and scale-free networks subject to vertex and edge attacks, Phys A: stat mech appl, (2009)
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.