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 detectionconcentrationrandom graphsgraph Laplaciansparse 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)

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

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)