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

Abstract

Consider any random graph model where potential edges appear independently, with possibly different probabilities, and assume that the minimum expected degree is omega(ln n). 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. While this may seem surprising, we will see that this matrix concentration phenomenon is a generalization of known results about the Erös-Rényi model. In particular, we will argue that matrix concentration is implicit the theory of quasi-random graph properties. We present two main applications of the main result. In bond percolation over a graph G, we show that the Laplacian of the random subgraph is typically very close to the Laplacian of G. As a corollary, we improve upon a bound for the spectral gap due to Chung and Horn that was derived via much more complicated methods. In inhomogeneous random graphs, there are points X_1,...,X_n uniformly distributed on the interval [0,1] and each pair is connected with probability p kappa(X_i,X_j). We show that if \ln n/n<< p<< 1 and kappa is bounded, then the adjacency matrix of the random graph is close to an integral operator defined in terms of kappa. Our main proof tool is a new concentration inequality for matrix martingales that generalizes Freedman's inequality for the standard scalar setting.

46 pages, submitted

References in corpus (4)

• Relating quantum privacy and quantum coherence: an operational approach
• Percolation on dense graph sequences
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Words Maps and Spectra of Random Graph Lifts

Cited by in corpus (66)

• Matrix estimation by Universal Singular Value Thresholding
• Statistical inference on random dot product graphs: a survey
• Online Clustering of Bandits
• Consistent estimation of dynamic and multi-layer block models
• Matrix concentration inequalities via the method of exchangeable pairs
• Concentration for random product formulas
• Quantum linear systems algorithms: a primer
• Estimation from Pairwise Comparisons: Sharp Minimax Bounds with Topology Dependence
• Universally consistent vertex classification for latent positions graphs
• Noncommutative Bennett and Rosenthal inequalities
• Role of normalization in spectral clustering for stochastic blockmodels
• Sparse random graphs: regularization and concentration of the Laplacian
• A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference
• Two-sample Hypothesis Testing for Inhomogeneous Random Graphs
• The Golden-Thompson inequality --- historical aspects and random matrix applications
• Bootstrapping Networks with Latent Space Structure
• Subadditivity of Matrix phi-Entropy and Concentration of Random Matrices
• Impact of regularization on Spectral Clustering
• Unified ${\ell }_{2\to \infty }$ Eigenspace Perturbation Theory for Symmetric Random Matrices
• Laplacian Eigenmaps from Sparse, Noisy Similarity Measurements
• Calibrated Elastic Regularization in Matrix Completion
• Estimating Mixed Memberships with Sharp Eigenvector Deviations
• Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral
• Dimension-free tail inequalities for sums of random matrices
• Regularized spectral methods for clustering signed networks
• Matrix Concentration for Products
• Two-sample Test of Community Memberships of Weighted Stochastic Block Models
• A central limit theorem for scaled eigenvectors of random dot product graphs
• Dynamic Hidden-Variable Network Models
• Robust Estimation from Multiple Graphs under Gross Error Contamination
• Pattern Formation in Random Networks Using Graphons
• Thermodynamics of network model fitting with spectral entropies
• Freedman's inequality for matrix martingales
• Concentration of OTOC and Lieb-Robinson velocity in random Hamiltonians
• Covariate Regularized Community Detection in Sparse Graphs
• OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits
• Universally Consistent Latent Position Estimation and Vertex Classification for Random Dot Product Graphs
• Noncommutative martingale deviation and Poincaré type inequalities with applications
• Spectra of edge-independent random graphs
• Efficient Estimation for Random Dot Product Graphs via a One-step Procedure
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs
• Probability inequalities for high dimensional time series under a triangular array framework
• The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks
• Concentration Inequalities for Sums of Markov Dependent Random Matrices
• Hypothesis Testing for Equality of Latent Positions in Random Graphs
• Multiple Network Embedding for Anomaly Detection in Time Series of Graphs
• Out-of-sample Extension for Latent Position Graphs
• From Poincaré Inequalities to Nonlinear Matrix Concentration
• Concentration for matrix martingales in continuous time and microscopic activity of social networks
• Large Cuts in Hypergraphs via Energy
• A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees
• Limit theorems for out-of-sample extensions of the adjacency and Laplacian spectral embeddings
• Asymptotics of the spectral radius for directed Chung-Lu random graphs with community structure
• Numerical tolerance for spectral decompositions of random matrices
• Spectral signatures of structural change in financial networks
• Synchronization of coupled chaotic maps
• Edge sampling using network local information
• Kolmogorov's law of the iterated logarithm for noncommutative martingales
• On Bernstein Type Exponential Inequalities for Matrix Martingales
• On-off Threshold Models of Social Contagion
• On Azuma-type inequalities for Banach space-valued martingales
• Sharp concentration for sums of matrices with Markovian dependence through universality
• Sparse recovery with unknown variance: a LASSO-type approach
• Lost chapter of Physical Chemistry means convergence between Fisher Kolmogorov equation and tunnel effect
• Concentration of the Stationary Distribution on General Random Directed Graphs
• Algebraic Connectivity Under Site Percolation in Finite Weighted Graphs