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.
Keywords
Giant componentRandom graphDegree distributionBipartite graphVertex (graph theory)CombinatoricsIndifference graphDegree (music)MathematicsDiscrete mathematicsChordal graphPathwidthComplex networkGraphLine graphPhysics
Affiliated Institutions
Related Publications
Are randomly grown graphs really random?
We analyze a minimal model of a growing network. At each time step, a new vertex is added; then, with probability delta, two vertices are chosen uniformly at random and joined b...
GraRep
In this paper, we present {GraRep}, a novel model for learning vertex representations of weighted graphs. This model learns low dimensional vectors to represent vertices appeari...
Partitioning Sparse Matrices with Eigenvectors of Graphs
The problem of computing a small vertex separator in a graph arises in the context of computing a good ordering for the parallel factorization of sparse, symmetric matrices. An ...
Co-clustering documents and words using bipartite spectral graph partitioning
Both document clustering and word clustering are well studied problems. Most existing algorithms cluster documents and words separately but not simultaneously. In this paper we ...
An improved index of centrality
Increasing interest in the application of graph theory to the behavioral sciences is evidenced by the 1963 publication of the book "Applications of Graph Theory to Group Structu...
Publication Info
- Year
- 2001
- Type
- article
- Volume
- 64
- Issue
- 2
- Pages
- 026118-026118
- Citations
- 3631
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
3631
OpenAlex
Cite This
M. E. J. Newman,
Steven H. Strogatz,
Duncan J. Watts
(2001).
Random graphs with arbitrary degree distributions and their applications.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics
, 64
(2)
, 026118-026118.
https://doi.org/10.1103/physreve.64.026118
Identifiers
- DOI
- 10.1103/physreve.64.026118