54
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Robustness of a Network of Networks

      Preprint
      , , ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Almost all network research has been focused on the properties of a single network that does not interact and depends on other networks. In reality, many real-world networks interact with other networks. Here we develop an analytical framework for studying interacting networks and present an exact percolation law for a network of \(n\) interdependent networks. In particular, we find that for \(n\) Erd\H{o}s-R\'{e}nyi networks each of average degree \(k\), the giant component, \(P_{\infty}\), is given by \(P_{\infty}=p[1-\exp(-kP_{\infty})]^n\) where \(1-p\) is the initial fraction of removed nodes. Our general result coincides for \(n=1\) with the known Erd\H{o}s-R\'{e}nyi second-order phase transition for a single network. For any \(n \geq 2\) cascading failures occur and the transition becomes a first-order percolation transition. The new law for \(P_{\infty}\) shows that percolation theory that is extensively studied in physics and mathematics is a limiting case (\(n=1\)) of a more general general and different percolation law for interdependent networks.

          Related collections

          Most cited references10

          • Record: found
          • Abstract: found
          • Article: found
          Is Open Access

          Error and attack tolerance of complex networks

          Many complex systems, such as communication networks, display a surprising degree of robustness: while key components regularly malfunction, local failures rarely lead to the loss of the global information-carrying ability of the network. The stability of these complex systems is often attributed to the redundant wiring of the functional web defined by the systems' components. In this paper we demonstrate that error tolerance is not shared by all redundant systems, but it is displayed only by a class of inhomogeneously wired networks, called scale-free networks. We find that scale-free networks, describing a number of systems, such as the World Wide Web, Internet, social networks or a cell, display an unexpected degree of robustness, the ability of their nodes to communicate being unaffected by even unrealistically high failure rates. However, error tolerance comes at a high price: these networks are extremely vulnerable to attacks, i.e. to the selection and removal of a few nodes that play the most important role in assuring the network's connectivity.
            Bookmark
            • Record: found
            • Abstract: found
            • Article: found
            Is Open Access

            Random graphs with arbitrary degree distributions and their applications

            Recent work on the structure of social networks and the internet has focussed attention on graphs with distributions of vertex degree that are significantly different from the Poisson degree distributions that have been widely studied in the past. In this paper we develop in detail the theory of random graphs with arbitrary degree distributions. In addition to simple undirected, unipartite graphs, we examine the properties of directed and bipartite graphs. Among other results, we derive exact expressions for the position of the phase transition at which a giant component first forms, the mean component size, the size of the giant component if there is one, the mean number of vertices a certain distance away from a randomly chosen vertex, and the average vertex-vertex distance within a graph. We apply our theory to some real-world graphs, including the world-wide web and collaboration graphs of scientists and Fortune 1000 company directors. We demonstrate that in some cases random graphs with appropriate distributions of vertex degree predict with surprising accuracy the behavior of the real world, while in others there is a measurable discrepancy between theory and reality, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.
              Bookmark
              • Record: found
              • Abstract: found
              • Article: found
              Is Open Access

              Network robustness and fragility: Percolation on random graphs

              Recent work on the internet, social networks, and the power grid has addressed the resilience of these networks to either random or targeted deletion of network nodes. Such deletions include, for example, the failure of internet routers or power transmission lines. Percolation models on random graphs provide a simple representation of this process, but have typically been limited to graphs with Poisson degree distribution at their vertices. Such graphs are quite unlike real world networks, which often possess power-law or other highly skewed degree distributions. In this paper we study percolation on graphs with completely general degree distribution, giving exact solutions for a variety of cases, including site percolation, bond percolation, and models in which occupation probabilities depend on vertex degree. We discuss the application of our theory to the understanding of network resilience.
                Bookmark

                Author and article information

                Journal
                27 October 2010
                Article
                10.1103/PhysRevLett.107.195701
                1010.5829
                2060b898-167e-4501-acc4-875bbc667dbf

                http://creativecommons.org/licenses/by/3.0/

                History
                Custom metadata
                Phys. Rev. Lett. 107, 195701 (2011)
                7 pages, 3 figures
                physics.data-an cs.SI physics.soc-ph

                Comments

                Comment on this article