Connected Components in Random Graphs with Given Expected Degree Sequences

By Fan Chung, Linyuan Lu. 2002

415 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

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

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 Geometry and Topology

Citations in the corpus

Eigenvalues of Random Power law Graphs (2003, methodology): “We will use a random graph model from [5], which is a generalization of the ErdősRényi model, for random graphs with given expected degrees w1, w2, .”
Synchronization from Second Order Network Connectivity Statistics (2011, positive): “As described in (Chung and Lu, 2002), as long as max i,j x i y j ≤ N ( N − 1) p , this approach yields a network whose distribution of expected degrees is given by p d ( x,y ).”
Graph Neural Networks Exponentially Lose Expressive Power for Node Classification (2019, background): “For example, Chung & Radcliffe (2011) proved the convergence of the spectral distribution of the normalized Laplacian for Chung-Lu’s model (Chung & Lu, 2002), which includes power law graphs as a special case (see, Theorem 4 of Chung & Radcliffe (2011)).”
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].”
Distances in Random Graphs with Finite Mean and Infinite Variance Degrees (2005, neutral): “A second related model can be found in [12, 13], where edges between nodes i and j are present with probability equal to wiwj/ ∑ l wl for some ‘expected degree vector’ w = (w1, .”
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.”
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].”
Novel scaling limits for critical inhomogeneous random graphs (2009, background): “3) and which has been studied intensively by Chung and Lu (see [13, 14, 15, 16, 17]).”