Communications in Nonlinear Science and Numerical Simulation
Vulnerability of complex networks
Introduction
In everyday life we are surrounded with complex networks; examples include social networks (collaboration networks), technological networks (communication networks, the Internet, power grids), information networks (the World Wide Web, language networks), biological networks (protein–protein interaction networks, neural networks, ecological networks) and etc. A central issue in the analysis of complex networks is the assessment of their robustness and vulnerability. Different approaches to address network robustness and vulnerability have recently been proposed by research community. The first approach is related to structural robustness [1], [2], [3], [4], [5]: how different classes of network topologies are affected by the removal of a finite number of links and/or nodes. It was concluded that the more heterogeneous a network is in terms of, e.g., degree distribution, the more robust it is to random failures, while, at the same time, it appears more vulnerable to deliberate attacks on highly connected nodes. In addition, the occurrence of blind spots (i.e. isolated nodes) can be of great interest when studying structural robustness in applications such as sensor networks. Using the percolation framework, this phenomenon is investigated in [6]. The second approach concerns dynamical robustness [7], [8], [9], [10]. For networks supporting the flow of a physical quantity, the removal of a node or link will cause the flow to redistribute with the risk that some other nodes or links may be overloaded and failure prone. Hence, a triggering event can cause a whole sequence of failures due to overload, and may even threaten the global stability of the network. Such behavior is termed cascading failure.
In general, the vulnerability of complex networks can be either node or edge vulnerability. One method of measuring node vulnerability is proposed in [11]. Latora and Marchiori measure the vulnerability of a node V(i) as relative drop in performance after removal of the ith node together with all the edges connected to it. Then they argue that the maximal value V of V(i) over all i corresponds to the network vulnerability. As an addition to this, authors in [12] introduce an additional parameter called the relative variance h. This parameter is a measure of the fluctuation level and it is used to describe the hierarchical properties of the network, and thus its vulnerability.
In this paper we consider the normalized average edge betweenness as a metric for network vulnerability. Recently a multi-scale measure for vulnerability of a graph is suggested by Boccaletti and his co-workers in [13]. In special case, when the multi-scale coefficient equals 1, it reduces to the average edge betweenness. We discuss relations of this metric to some graph characteristics. We also investigate how the normalized average edge betweenness fluctuates when certain nodes or edges are removed from the network. We measure the vulnerability of four synthetic networks: random (Erdős–Rényi) network, geometric random network, scale-free network, and small world network. Finally, we measure the vulnerability of different real world networks: the Erdős collaboration network, logical network of the brain, physical network of the brain, and EU and US power grid networks. The same analysis is also carried out for three urban transport networks: Turin’s, Milan’s and London’s road network.
The paper is organized as follows. Section 2 introduces a measure of network vulnerability called vulnerability index. In Section 3 we discuss vulnerability index for the synthetic networks. Section 4 summarizes the results of vulnerability analysis of real networks. Section 5 concludes this paper.
Section snippets
Network vulnerability
In this paper we consider networks that can be modeled as simple graphs. A graph is an ordered pair G = (V, E) comprising a set V of vertices or nodes together with a set E of edges or lines, which are 2-element subsets of V. A simple graph is an undirected graph that has no self-loops and no more than one edge between any two different vertices. Average edge betweenness of the graph G is defined as [13]:where ∣E∣ is the number of the edges, and bl is the edge betweenness of the
Vulnerability index for synthetic networks
In this section we discuss vulnerability of several synthetic networks.
- •
Erdős Rényi (ER) random networks – The random network of Erdős and Rényi is a prototypical model for complex networks. An ER network with N nodes is constructed by linking each pair of nodes with the probability b/[(N − 1)/2], or by adding bN links between randomly selected pairs of nodes, where the link density is given by b and the degree distribution follows the Poisson distribution with the mean degree 〈k〉= 2b. For ER
Vulnerability index for real networks
In this section we consider several real-world networks.
- •
Human brain network – It represents the structural connectivity of the entire human brain. The data are obtained by a diffusion magnetic resonance imaging (MRI) scan [20]. The network has two layers: physical and logical. The logical layer consists of connections in the gray matter in the brain, while the physical layer reflects the axonal wiring used to establish the logical connections. The logical brain network (LB) is consisted of 1013
Conclusion
In this paper we have suggested that normalized average edge betweenness together with its relative difference when certain number of nodes and/or edges are removed from the network forms a triple that can be used as a measure of network vulnerability (called vulnerability index). WS model of small-world network appears to be the most robust network among all synthetic networks studied in the paper. This conclusion is due to the fact that this model shows highest structural robustness when
References (22)
- et al.
The anatomy of a large-scale hypertextual web search engine
Comput Netw ISDN Syst
(1998) - et al.
Statistical mechanics of complex networks
Rev Mod Phys
(2002) - et al.
The diameter of the world wide web
Nature (London)
(1999) A simple model of global cascades on random networks
Proc Natl Acad Sci USA
(2002)- et al.
Attack vulnerability of complex networks
Phys Rev E
(2002) - et al.
Structural vulnerability of the North American power grid
Phys Rev E
(2004) - et al.
Percolation and blind spots in complex networks
Phys Rev E
(2006) - et al.
Cascade-based attacks on complex networks
Phys Rev E
(2002) Cascade control and defense in complex networks
Phys Rev Lett
(2004)- et al.
Model for cascading failures in complex networks
Phys Rev E
(2004)
Geographical effects on cascading breakdowns of scale-free networks
Phys Rev E
Cited by (112)
A hybrid modified-NSGA-II VNS algorithm for the Multi-Objective Critical Disruption Path Problem
2023, Computers and Operations ResearchMining of book-loan behavior based on coupling relationship analysis
2023, Physica A: Statistical Mechanics and its ApplicationsCross-sectoral preparedness and mitigation for networked typhoon disasters with cascading effects
2022, Urban ClimateCitation Excerpt :Specifically, the removal of node degree centrality and betweenness centrality mean the nodes are first ranked in descending order of the node degree centrality and betweenness centrality in urban disaster networks. Then, nodes are removed one by one since the highest value node (Mishkovski et al., 2011; Ma et al., 2020). There are two strategies used for edge removal analysis: edge betweenness centrality removal and random removal.
Robust analysis of cascading failures in complex networks
2021, Physica A: Statistical Mechanics and its ApplicationsCitation Excerpt :The robustness of complex networks can be considered from static and dynamic perspectives. The static perspective is in view of network structure [1–9], which considers how the topological properties of networks are affected by removing various points and edges from the network. The second type concerns dynamical robustness in view of cascading failures [10–18].
Energy disruptive centrality with an application to criminal network
2021, Communications in Nonlinear Science and Numerical SimulationSimulation-based vulnerability assessment in transit systems with cascade failures
2021, Journal of Cleaner Production