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
- Remco van der Hofstad
- Mark Newman
- M. A. Porter
- Svante Janson
- Alex Arenas
- Oliver Riordan
- Linyuan Lu
- Béla Bollobás
In Statistical and Nonlinear Physics
- Mark Newman
- Santo Fortunato
- Remco van der Hofstad
- Jure Leskovec
- Marc Barthelemy
- Olaf Sporns
- Albert-László Barabási
- Alex Arenas
Citations in the corpus
- The statistical physics of real-world networks (2018, background): “The ‘bottom-up’ approach initially assigns to each node a number of link stubs equal its target degree; then, pairs of stubs are randomly matched avoiding the formation of self-loops and multi-links [157–159].”
- Graph mining: Laws, generators, and algorithms (2006, neutral): “CC → 0 PLOD [Palmer and Steffan 2000] for large N Exponential cutoff O(log N) CC → 0 [Newman et al. 2001] for large N BA [Barabási and Albert 1999] O(log N) or CC ∝ N O( log N log log N ) Initial attractiveness [Dorogovtsev and Mendes 2003] AB [Albert and Barabási 2000] Edge copying [Kleinberg et al”
- Characterization of complex networks: A survey of measurements (2005, methodology): “uch stubs are selected uniformly and joined together to form an edge. When all stubs have been used up, a random graph that is a member of the ensemble of graphs with that degree sequence is obtained [51, 52, 53]. Another possibility, the rewiring method, is to start with a network (possibly a real ”
- The Small World of Corporate Boards (2006, neutral): “The first of the clustering measures, used for example by Watts and Strogatz in Watts (1999b), begins by defining a clustering coefficient for each vertex.”
- Stations, trains and small-world networks (2003, background): “[5] have given expressions for average values of the network properties de:ned above, for various distributions of vertex degree, in terms of their generating functions.”
- Bipartite Graphs as Models of Complex Networks (2003, background): “Some of these properties, and others, have been studied independently in [55, 56] with different techniques and a different point of view.”
- Probability based estimation theory for respondent driven sampling (2008, background): “In pure random networks (Erdős and Renyi 1959; Newman et al. 2001), path length grows logarithmically with population size.”
- Metastable densities for the contact process on power law random graphs (2013, background): “degree distribution, as described in [13] and [8].”
- A Path Following Algorithm for the Graph Matching Problem (2008, background): “Our choice of random graph types is based on [37], where the authors discuss different types of random graphs which are the most frequently observed in various real-world applications (World Wide Web, collaborations networks, social networks, etc.”
- Multirelational organization of large-scale social networks in an online world (2010, neutral): “used in [48, 49]) and discard indirect interactions such as mere participation in a chat.”
- Comparing Community Structure to Characteristics in Online Collegiate Social Networks (2008, methodology): “Subtracting the fraction of expected edges in (2.1) corresponds to a specific choice of null model, suggested by Newman and Girvan [73,75], with average degree equal to that of the corresponding configuration model [ 77 ] (a random graph with an arbitrary, specified degree distribution).”
- The Friendship Paradox and Systematic Biases in Perceptions and Social Norms (2016, background): “8For more discussion of this, see Newman, Strogatz, and Watts (2001) and Section 4.2 of Jackson (2008).”
- Structure of growing social networks. (2001, background): “(The clustering coefficient can in fact be defined precisely as a measure of the density of such triangles [31].”