Concentration and regularization of random graphs

DOI10.1002/RSA.20713MaRDI QIDQ5371146zbMATH OpenOpenAlexFDO

Authors Can M. Le, Elizaveta Levina, Roman Vershynin

Publication date 24 October 2017

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.00669

zbMATH Keywords

community detectionconcentrationgraph Laplacianrandom graphssparse networks

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Abstract: This paper studies how close random graphs are typically to their expectations. We interpret this question through the concentration of the adjacency and Laplacian matrices in the spectral norm. We study inhomogeneous Erd"os-R'enyi random graphs on $n$ vertices, where edges form independently and possibly with different probabilities $p_{ij}$. Sparse random graphs whose expected degrees are $o(logn)$ fail to concentrate; the obstruction is caused by vertices with abnormally high and low degrees. We show that concentration can be restored if we regularize the degrees of such vertices, and one can do this in various ways. As an example, let us reweight or remove enough edges to make all degrees bounded above by $O(d)$ where $d=maxn{p}_{ij}$. Then we show that the resulting adjacency matrix $A^{\prime }$ concentrates with the optimal rate: $|A^{\prime }-mathbbEA|=O(sqrtd)$. Similarly, if we make all degrees bounded below by $d$ by adding weight $d/n$ to all edges, then the resulting Laplacian concentrates with the optimal rate: $|L(A^{\prime })-L(mathbbE{A}^{\prime })|=O(1/sqrtd)$. Our approach is based on Grothendieck-Pietsch factorization, using which we construct a new decomposition of random graphs. We illustrate the concentration results with an application to the community detection problem in the analysis of networks.

Recommendations

• CONCENTRATION OF RANDOM GRAPHS AND APPLICATION TO COMMUNITY DETECTION
• Sparse regular random graphs: spectral density and eigenvectors
• On the spectra of general random graphs
• Concentration of the spectral norm of Erdős-Rényi random graphs
• Sparse random tensors: concentration, regularization and applications

Cited in

(70)

• Two-sample hypothesis testing for inhomogeneous random graphs
• Coverings of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries
• Norms of random matrices: local and global problems
• Estimating a network from multiple noisy realizations
• On semidefinite relaxations for the block model
• Random Laplacian matrices and convex relaxations
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Spectral edge in sparse random graphs: upper and lower tail large deviations
• Sparse random tensors: concentration, regularization and applications
• On the spread of influence in graphs
• An approximation algorithm for the maximum spectral subgraph problem
• Global and individualized community detection in inhomogeneous multilayer networks
• Long time dynamics for interacting oscillators on graphs
• Overlapping community detection in networks via sparse spectral decomposition
• Sparse and smooth: improved guarantees for spectral clustering in the dynamic stochastic block model
• Concentration of the spectral norm of Erdős-Rényi random graphs
• Concentration and consistency results for canonical and curved exponential-family models of random graphs
• Vertex nomination, consistent estimation, and adversarial modification
• Network classification with applications to brain connectomics
• The Kato-Temple inequality and eigenvalue concentration with applications to graph inference
• Convexified modularity maximization for degree-corrected stochastic block models
• Largest eigenvalues of sparse inhomogeneous Erdős-Rényi graphs
• Concentration for Poisson functionals: component counts in random geometric graphs
• Spectral norm bounds for block Markov chain random matrices
• Statistical inference on random dot product graphs: a survey
• scientific article; zbMATH DE number 7049740 (Why is no real title available?)
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Quantum query algorithms are completely bounded forms
• Change point estimation in a dynamic stochastic block model
• Recovering structured probability matrices
• Ranking and synchronization from pairwise measurements via SVD
• Moments of uniform random multigraphs with fixed degree sequences
• scientific article; zbMATH DE number 7626779 (Why is no real title available?)
• Randomized Spectral Clustering in Large-Scale Stochastic Block Models
• Optimal and algorithmic norm regularization of random matrices
• Find Your Place: Simple Distributed Algorithms for Community Detection
• CONCENTRATION OF RANDOM GRAPHS AND APPLICATION TO COMMUNITY DETECTION
• Inference for multiple heterogeneous networks with a common invariant subspace
• Nonparametric modeling of higher-order interactions via hypergraphons
• A spectral method for community detection in moderately sparse degree-corrected stochastic block models
• Hierarchical Community Detection by Recursive Partitioning
• Community detection and percolation of information in a geometric setting
• Optimization via low-rank approximation for community detection in networks
• Modularity Maximization for Graphons
• Outliers in spectrum of sparse Wigner matrices
• Graphon convergence of random cographs
• Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
• Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
• Spectral Estimation of Large Stochastic Blockmodels with Discrete Nodal Covariates
• Concentration in gossip opinion dynamics over random graphs
• Two-sample test of stochastic block models
• Extreme singular values of inhomogeneous sparse random rectangular matrices
• Community detection in complex networks: from statistical foundations to data science applications
• A survey on theoretical advances of community detection in networks
• Target set in threshold models
• PCABM: Pairwise Covariates-Adjusted Block Model for Community Detection
• Network Estimation by Mixing: Adaptivity and More
• Comment: Ridge Regression and Regularization of Large Matrices
• Two-sample test of stochastic block models via the maximum sampling entry-wise deviation
• Optimal and exact recovery on the general nonuniform hypergraph stochastic block model
• Almost exact recovery in noisy semi-supervised learning
• Partial recovery and weak consistency in the non-uniform hypergraph stochastic block model
• Orthogonal symmetric non-negative matrix factorization under the stochastic block model
• Semiparametric modeling and analysis for longitudinal network data
• Novel network trimming for robust vertex nomination in contaminated networks
• Opinion diffusion in graphs: an adversarial approach
• ACRONYM: Augmented Degree Corrected, Community Reticulated Organized Network Yielding Model
• Community detection in sparse networks via Grothendieck's inequality
• Constructive regularization of the random matrix norm
• Estimating the number of communities by spectral methods

This page was built for publication: Concentration and regularization of random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5371146)