Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs

DOI10.1214/16-AOP1142zbMath1386.05174arXiv1501.06087OpenAlexW4298311822MaRDI QIDQ1747747

Marc Lelarge, Laurent Massoulié, Charles Bordenave

Publication date: 27 April 2018

Published in: The Annals of Probability (Search for Journal in Brave)

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

zbMATH Keywords

random graphsspectral gapcommunity detectionnonbacktracking matrix

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Inference from stochastic processes and spectral analysis (62M15) Applications of branching processes (60J85) Random matrices (algebraic aspects) (15B52) Directed graphs (digraphs), tournaments (05C20)

Related Items

Spectral gap in random bipartite biregular graphs and applications ⋮ Rate optimal Chernoff bound and application to community detection in the stochastic block models ⋮ Detection thresholds in very sparse matrix completion ⋮ Mixing time of PageRank surfers on sparse random digraphs ⋮ Community detection in the sparse hypergraph stochastic block model ⋮ There is no going back: properties of the non-backtracking Laplacian ⋮ The limit theorem with respect to the matrices on non-backtracking paths of a graph ⋮ Entrywise eigenvector analysis of random matrices with low expected rank ⋮ Learning sparse graphons and the generalized Kesten-Stigum threshold ⋮ Spectral theory of the non-backtracking Laplacian for graphs ⋮ Asymptotic Absence of Poles of Ihara Zeta Function of Large Erdős–Rényi Random Graphs ⋮ Non-backtracking spectra of weighted inhomogeneous random graphs ⋮ Spectral radii of sparse random matrices ⋮ The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime ⋮ Maximum likelihood estimation of sparse networks with missing observations ⋮ Unnamed Item ⋮ Contiguity and non-reconstruction results for planted partition models: the dense case ⋮ Community Detection and Stochastic Block Models ⋮ Estimating the number of communities by spectral methods ⋮ Spectral gap of sparse bistochastic matrices with exchangeable rows ⋮ Detecting a planted community in an inhomogeneous random graph ⋮ Reversibility of the non-backtracking random walk ⋮ The spectral gap of sparse random digraphs ⋮ Community detection in sparse networks via Grothendieck's inequality ⋮ Recent results of quantum ergodicity on graphs and further investigation ⋮ Sparse random tensors: concentration, regularization and applications ⋮ Community detection with dependent connectivity ⋮ Exact recovery in the hypergraph stochastic block model: a spectral algorithm ⋮ The spectral norm of random lifts of matrices ⋮ Eigenvalues of random lifts and polynomials of random permutation matrices ⋮ Global and individualized community detection in inhomogeneous multilayer networks ⋮ Eigenvalues of the non-backtracking operator detached from the bulk ⋮ Top eigenpair statistics for weighted sparse graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A sharp version of Bauer-Fike's theorem
• Reconstruction and estimation in the planted partition model
• Ramanujan graphs
• The eigenvalues of random symmetric matrices
• On the second eigenvalue of a graph
• Automorphic forms and geometry of arithmetic varieties
• A proof of the block model threshold conjecture
• Recurrence of distributional limits of finite planar graphs
• Spectral redemption in clustering sparse networks
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• Expander graphs and their applications
• A proof of Alon’s second eigenvalue conjecture and related problems
• Diameters and Eigenvalues
• An Introduction to Stein's Method
• The non-backtracking spectrum of the universal cover of a graph
• Community detection thresholds and the weak Ramanujan property
• The phase transition in inhomogeneous random graphs
• A Limit Theorem for Multidimensional Galton-Watson Processes
• Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes