Random graphs with arbitrary degree distributions and their applications.

By Mark Newman, Steven H. Strogatz, Duncan J. Watts. Physical review. E, Statistical, nonlinear, and soft matter physics, 2000

3,585 citations recorded by the source corpus.

Recent work on the structure of social networks and the internet has focused 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.

Subfields: Geometry and Topology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/e8b8c5f4a81e11576ee2c74ab65c66a42bbad270

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Geometry and Topology

  1. Remco van der Hofstad
  2. Mark Newman
  3. M. A. Porter
  4. Svante Janson
  5. Alex Arenas
  6. Oliver Riordan
  7. Linyuan Lu
  8. Béla Bollobás

In Statistical and Nonlinear Physics

  1. Mark Newman
  2. Santo Fortunato
  3. Remco van der Hofstad
  4. Jure Leskovec
  5. Marc Barthelemy
  6. Olaf Sporns
  7. Albert-László Barabási
  8. Alex Arenas

Citations in the corpus