The average distances in random graphs with given expected degrees

By Fan Chung, Linyuan Lu. 2002

929 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Statistical and Nonlinear Physics, Scaling & Learning Theory, Algorithms & Complexity

How researchers see this paper

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

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Statistical and Nonlinear Physics

In Scaling & Learning Theory

In Algorithms & Complexity

Citations in the corpus

Big Bird: Transformers for Longer Sequences (2020, background): “In such a random graph with just ˜ ⇥ ( n ) edges, the shortest path between any two nodes is logarithmic in the number of nodes [17, 43].”
Concentration Inequalities and Martingale Inequalities: A Survey (2006, background): “[Chung and Lu 02b] Let X1, . . . , Xn be independent random variables with Pr(Xi = 1) = pi, Pr(Xi = 0) = 1− pi.”
Characterization of complex networks: A survey of measurements (2005, methodology): “esults presented in Section 16.2. Due to its importance and amenability to analytical treatment, many works deal with this model, including the papers of Newman [23], Aiello et al. [55], Chung and Lu [56] and Cohen and Havlin [57]. 3.4 Scale-free Networks of Barabási and Albert After Watts and Strog”
Novel scaling limits for critical inhomogeneous random graphs (2009, neutral): “3) and which has been studied intensively by Chung and Lu (see [13, 14, 15, 16, 17]).”
The Economic Consequences of Social Network Structure (2017, positive): “…have been proven for increasingly rich network models, starting from simple ones (Erdős and Rényi (1959)), to ones with richer degree distributions (Chung and Lu (2002)), to ones rewired from networks with high clustering (Watts and Strogatz (1998)), to ones with rich sets of node…”
Distances in random graphs with infinite mean degrees (2004, background): “Firstly, the actual degree vector in [6] should be close to the expected degree vector.”
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters (2008, methodology): “Here we work with the random graph model with given expected degrees, as described by Chung and Lu [42, 40, 44, 39, 41, 45, 46, 43].”
Network biology: understanding the cell's functional organization (2004, background): “Although the small-world effect is a property of random networks, scale-free networks are ultra smal”
Scale-free percolation (2011, neutral): “We mention also the expected degree model by Chung and Lu [13, 14] and the related generalized random graph [12], which are in the same universality class as the Poissonian random graph model.”
Modeling interactome: scale-free or geometric? (2004, background): “the diameter of Erdös–Rényi random networks on n nodes is proportional to logn, the network property often referred to as the small-world property; the diameters of scale-free random networks with degree exponent 2 < γ < 3, which have been observed for most real-world networks, are ultra-small (Chun”