• Free to Read

Random graphs with arbitrary degree distributions and their applications

M. E. J. Newman, S. H. Strogatz, and D. J. Watts
Phys. Rev. E 64, 026118 – Published 24 July 2001
An article within the collection: PRE Milestones and the Physical Review E 25th Anniversary Milestones
PDFExport Citation

Abstract

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.

  • Received 19 March 2001

DOI:https://doi.org/10.1103/PhysRevE.64.026118

©2001 American Physical Society

Collections

This article appears in the following collections:

PRE Milestones

Physical Review E published its 50,000th paper in September 2015. To celebrate this, the journal presents a series of milestone papers that were published since its inception in 1993. This is an eclectic collection of papers that made significant contributions to their field, chosen by the editors. A new milestone will be added each week.

Physical Review E 25th Anniversary Milestones

The year 2018 marks the 25th anniversary of Physical Review E. To celebrate the journal’s rich legacy, during the upcoming year we highlight a series of papers that made important contributions to their field. These milestone articles were nominated by members of the Editorial Board of Physical Review E, in collaboration with the journal’s editors. The 25 milestone articles, including an article for each calendar year from 1993 through 2017 and spanning all major subject areas of the journal, will be unveiled in chronological order and will be featured on the journal website.

Authors & Affiliations

M. E. J. Newman1,2, S. H. Strogatz2,3, and D. J. Watts1,4

  • 1Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501
  • 2Center for Applied Mathematics, Cornell University, Ithaca, New York 14853-3401
  • 3Department of Theoretical and Applied Mechanics, Cornell University, Ithaca, New York 14853-1503
  • 4Department of Sociology, Columbia University, 1180 Amsterdam Avenue, New York, New York 10027

References

Click to Expand
Issue

Vol. 64, Iss. 2 — August 2001

Reuse & Permissions
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×