Vulnerability of complex networks

https://doi.org/10.1016/j.cnsns.2010.03.018Get rights and content

Abstract

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.

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]:b(G)=1|E|lEbl,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)

  • S. Brin et al.

    The anatomy of a large-scale hypertextual web search engine

    Comput Netw ISDN Syst

    (1998)
  • R. Albert et al.

    Statistical mechanics of complex networks

    Rev Mod Phys

    (2002)
  • R. Albert et al.

    The diameter of the world wide web

    Nature (London)

    (1999)
  • D.J. Watts

    A simple model of global cascades on random networks

    Proc Natl Acad Sci USA

    (2002)
  • P. Holme et al.

    Attack vulnerability of complex networks

    Phys Rev E

    (2002)
  • R. Albert et al.

    Structural vulnerability of the North American power grid

    Phys Rev E

    (2004)
  • L. Huang et al.

    Percolation and blind spots in complex networks

    Phys Rev E

    (2006)
  • A.E. Motter et al.

    Cascade-based attacks on complex networks

    Phys Rev E

    (2002)
  • A.E. Motter

    Cascade control and defense in complex networks

    Phys Rev Lett

    (2004)
  • P. Crucitti et al.

    Model for cascading failures in complex networks

    Phys Rev E

    (2004)
  • L. Huang et al.

    Geographical effects on cascading breakdowns of scale-free networks

    Phys Rev E

    (2006)
  • Cited by (112)

    • Mining of book-loan behavior based on coupling relationship analysis

      2023, Physica A: Statistical Mechanics and its Applications
    • Cross-sectoral preparedness and mitigation for networked typhoon disasters with cascading effects

      2022, Urban Climate
      Citation 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 Applications
      Citation 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 Simulation
    View all citing articles on Scopus
    View full text