The Spectra of Random Graphs with Given Expected Degrees

By Fan Chung Graham, Linyuan Lu, Van H. Vu. Internet Mathematics, 2004

428 citations recorded by the source corpus.

Subfields: Mathematical Physics, Statistical and Nonlinear Physics, Statistics and Probability

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

How researchers see this paper

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

In Mathematical Physics

In Statistical and Nonlinear Physics

In Statistics and Probability

Citations in the corpus

Critical phenomena in complex networks (2007, background): “However, in an uncorrelated random complex network, the maximum eigenvalue λmax is determined by the cutoff qcut(N) of the degree distribution, λmax ≈ q cut (N) (Chung et al., 2003; Dorogovtsev et al., 2003; Krivelevich and Sudakov, 2003). In scale-free networks ( γ <∞), the cutoff diverges in the l”
Anomaly detection in dynamic networks: a survey (2015, methodology): “Vertex detection [55, 56, 67, 106] Subgraph detection [3, 13, 30, 31] Change detection [38] Edge detection [22] Change detection [112] Vertex detection [129] Event detection [68, 72, 75, 77, 83, 84, 93, 113, 114, 115, 122] Change detection [7, 65, 66] Edge detection [1, 80] Subgraph detection [60, 8”
AWB-GCN: A Graph Convolutional Network Accelerator with Runtime Workload Rebalancing (2019, background): “rs, the GCN is able to extract very high-level abstracted features for various learning purposes. 2.2 Characteristics of Power-Law Graphs Real-world graphs typically follow the power-law distribution [3,4,12,40], which states that the number of nodes y of a given degree x is proportional to x b for ”
Spectral Gaps of Random Graphs and Applications (2012, background): “Improvements and corrections to this argument brought the bound to p = ω(log4 n/n), [43] and later to as low as p log2 n/n [8].”
Statistical properties of community structure in large social and information networks (2008, methodology): “Eigenvalues of power law graphs have also been studied by Mihail and Papadimitriou [117], Chung, Lu, Vu [43, 44, 45], and Flaxman, Frieze, and Fenner [69].”
ALGEBRAIC CONNECTIVITY OF ERDÖS-RÉNYI GRAPHS NEAR THE CONNECTIVITY THRESHOLD (2014, methodology): “Chung, Lu and Vu [11] later improved this estimate in the case of the normalized Laplacian L = D− 12LD− 12 by using the trace method.”
The Kuramoto model in complex networks (2015, background): “In particular, for uncorrelated networks with a given degree distribution we have that [59]”
A Survey of Statistical Network Models (2009, methodology): “.g.,239], and they either x the degree-distribution parameters or compute distributions that are conditional on some function of the degree distributions or sequences, such as their expectations (cf. [235;70]). Software is available to sample from the space of random graphs with a given degree distr”
Toward link predictability of complex networks (2015, neutral): “If p is finite and the network size N goes to infinity, the spectral density adjacency matrices in ER networks obey the Wigner semicircle law and the eigenvectors are distributed isotropically at random (29, 30).”
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].”
Random walks in peer-to-peer networks (2004, methodology): “We use expanders since expansion is desired and believed to hold in every reasonable network and network model [2], [18], [19].”
Distribution of subgraphs of random regular graphs (2008, background): “It was shown in [23] that the eigenvalue distribution of M(G) for a random graph G with a given expected degree distribution satisfies the semi-circle law if the minimum degree is greater than a power of log n.”
Discrete-time Markov chain approach to contact-based disease spreading in complex networks (2009, methodology): “For the RP corresponding to the SIS spreading process usually adopted [8], the classical result for uncorrelated SF networks is recovered because, in this case, the largest eigenvalue [35,36] is Λmax = 〈k (2)〉/〈k〉.”
Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges (2009, methodology): “One of them is the “trace method” [26, 28, 38, 35, 36] which consists of analyzing traces of high powers of the matrices under consideration.”
Graph Neural Networks Exponentially Lose Expressive Power for Node Classification (2019, methodology): “We choose the eigenvector e ∈ R Chung et al. (2004) and Coja-Oghlan (2007) proved similar theorems.”
The structure and dynamics of multilayer networks (2014, methodology): “For the RP corresponding to the SIS spreading process, instead, the largest eigenvalue must be calculated [236].”
Size biased couplings and the spectral gap for random regular graphs (2015, methodology): “However, it is more flexible in some ways than the trace method: it has been adapted to establish bounds on the spectral gap for several other random graph models (see, for instance, [15, 19, 20, 25, 29, 40, 42]), and it can be applied when d grows with n, as observed in [15].”