Blog
About

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

      Random graphs with arbitrary degree distributions and their applications

      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

          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.

          Related collections

          Most cited references 12

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

          Emergence of scaling in random networks

          Systems as diverse as genetic networks or the world wide web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution. This feature is found to be a consequence of the two generic mechanisms that networks expand continuously by the addition of new vertices, and new vertices attach preferentially to already well connected sites. A model based on these two ingredients reproduces the observed stationary scale-free distributions, indicating that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.
            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            A critical point for random graphs with a given degree sequence

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

              The structure of scientific collaboration networks

                (2009)
              We investigate the structure of scientific collaboration networks. We consider two scientists to be connected if they have authored a paper together, and construct explicit networks of such connections using data drawn from a number of databases, including MEDLINE (biomedical research), the Los Alamos e-Print Archive (physics), and NCSTRL (computer science). We show that these collaboration networks form "small worlds" in which randomly chosen pairs of scientists are typically separated by only a short path of intermediate acquaintances. We further give results for mean and distribution of numbers of collaborators of authors, demonstrate the presence of clustering in the networks, and highlight a number of apparent differences in the patterns of collaboration between the fields studied.
                Bookmark

                Author and article information

                Journal
                13 July 2000
                2001-05-07
                Article
                10.1103/PhysRevE.64.026118
                cond-mat/0007235
                Custom metadata
                Santa Fe Institute working paper 00-07-042
                Phys. Rev. E 64, 026118 (2001)
                19 pages, 11 figures, some new material added in this version along with minor updates and corrections
                cond-mat.stat-mech cond-mat.dis-nn

                Condensed matter, Theoretical physics

                Comments

                Comment on this article