Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges

By Roberto Imbuzeiro Oliveira. 2009

213 citations recorded by the source corpus.

Consider any random graph model where potential edges appear independently, with possibly different probabilities, and assume that the minimum expected degree is !(lnn). We prove that the adjacency matrix and the Laplacian of that random graph are concentrated around the corresponding matrices of the weighted graph whose edge weights are the probabilities in the random model. We apply this result to two different settings. In bond percolation, we show that, whenever the minimum expected degree in the random model is not too small, the Laplacian of the percolated graph is typically close to that of the original graph. As a corollary, we improve upon a bound for the spectral gap of the percolated graph due to Chung and Horn.

Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology, Statistics and Probability

How researchers see this paper

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

In Discrete Mathematics and Combinatorics

In Geometry and Topology

In Statistics and Probability

Citations in the corpus

DeltaGrad: Rapid retraining of machine learning models (2020, methodology): “CLASSICAL RESULTS FOR RANDOM VARIABLES To analyze DeltaGrad with SGD, Bernsteins inequality (Oliveira, 2009; Tropp, 2012; 2016) is necessary.”
User-Friendly Tail Bounds for Sums of Random Matrices (2010, methodology): “More sophisticated martingale results require additional machinery [39, 55].”
A Limit Theorem for Scaled Eigenvectors of Random Dot Product Graphs (2013, background): “More recently, general bounds for the operator norm of the difference between the adjacency matrix and its expectation have been proved in Oliveira (2010) and Tropp (2011).”
Matrix concentration inequalities via the method of exchangeable pairs (2012, unknown): “(5.2)”
ALGEBRAIC CONNECTIVITY OF ERDÖS-RÉNYI GRAPHS NEAR THE CONNECTIVITY THRESHOLD (2014, methodology): “Oliviera [33] and later Chung and Radcliffe [12] improved this result by using a new class of matrix concentration inequalities for random matrices.”
Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence (2015, methodology): “Using standard matrix concentration inequalities, it is straightforward to extend our analysis to the setting of random chosen comparisons from a ﬁxed graph (see, for instance, Oliveira (2009)).”
Online Clustering of Bandits (2014, methodology): “We are now in a position to apply a Freedman-like inequality for matrix martingales due to (Oliveira, 2010; Tropp, 2011) to the (matrix) martingale difference sequence E1[x̄1x̄1 | c1]− x̄1x̄1 , E2[x̄2x̄2 | c2]− x̄2x̄2 , .”
Noncommutative martingale deviation and Poincaré type inequalities with applications (2012, methodology): “We would like to thank Joel Tropp for bringing Oliveira’s paper [25] to our attention.”
Randomized numerical linear algebra: Foundations and algorithms (2020, methodology): “) Parker also observed that structured random matrices (such as the randomized trigonometric transforms from Section 9.3) allow us to perform the preconditioning step at lower cost than the subsequent Gaussian elimination procedure. Parker (1995) inspired many subsequent papers, including (Baboulin,”
The Masked Sample Covariance Estimator: An Analysis via Matrix Concentration Inequalities (2011, background): “This research was initiated in the paper Ahlswede –Winter [1] and continued in a variety of other works [14, 27, 30, 32, 37, 38].”
Statistical Inference on Random Dot Product Graphs: a Survey (2017, methodology): “We focus on the following important result of Oliveira [76] and Tropp [103] and further improvements of Lu and Peng [62] and Lei and Rinaldo [57], all of which establish that the A and P are close in spectral norm.”