The Average Distance in a Random Graph with Given Expected Degrees

By Fan Chung Graham, Linyuan Lu. Internet Mathematics, 2004

331 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Statistical and Nonlinear Physics

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

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

Citations in the corpus

Towards a Theory of Scale-Free Graphs: Definition, Properties, and Implications (2005, methodology): “…due to Erd¨os and Reny´ı [39]; (2) equilibrium random graphs with a given degree distribution such as the Generalized Random Graph (GRG) method [31]; (3) “small-world networks” due to Watts and Strogatz [100]; and (4) networks growing under the mechanism of preferential linking due to…”
Statistical properties of community structure in large social and information networks (2008, methodology): “We will work with the random graph model with given expected degrees, as described by Chung and Lu [41, 39, 43, 38, 40, 44, 45, 42].”
Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees (2013, methodology): “To generate a random power-law graph, we follow the Chung-Lu model [11]: we first generate a degree sequence (d1, .”
The phase transition in inhomogeneous random graphs (2005, background): “For example, Chung and Lu [35, 36] studied distances in a ‘random graph with given expected degrees’.”
Novel scaling limits for critical inhomogeneous random graphs (2009, unknown): “3) and which has been studied intensively by Chung and Lu (see [13, 14, 15, 16, 17]).”
Universality for first passage percolation on sparse random graphs (2012, background): “= wiwj ℓn +wiwj , (1.29) and the random graph with given prescribed degrees or Chung-Lu model, where instead pij = max(wiwj/ℓn,1), (1.30) 8 and which has been studied intensively by Chung and Lu (see [18, 19, 20, 21, 22]). Let W denote a random variable with distribution FW. By Janson [38], when Wn ”
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].”
First passage percolation on random graphs with finite mean degrees (2009, unknown): “Similar results have appeared for related models in [11, 16, 28].”
Contact processes on random graphs with power law degree distributions have critical value 0 (2009, background): “By Shirshendu Chatterjee and Rick Durrett1”
FENNEL: streaming graph partitioning for massive scale graphs (2014, methodology): “Specifically, we first generate a power-law degree sequence with a given slope δ and use the Chung-Lu random graph model to create an instance of a power law graph [5].”
Random Graphs and Complex Networks (2016, methodology): “The expected degree random graph, or Chung-Lu model, has been studied extensively by Chung and Lu in [75, 76, 77, 81, 183].”