Graph Powering and Spectral Robustness

DOI10.1137/19M1257135zbMath1484.62117arXiv1809.04818OpenAlexW3104381963MaRDI QIDQ5027021

Enric Boix-Adserà, Emmanuel Abbe, Colin Sandon, Peter Ralli

Publication date: 3 February 2022

Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

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

zbMATH Keywords

random graphsspectral algorithmscommunity detectionstochastic block modelsnetwork data analysisspectral embeddings

Mathematics Subject Classification ID

Bayesian inference (62F15) Robustness and adaptive procedures (parametric inference) (62F35) Inference from stochastic processes and spectral analysis (62M15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Rate optimal Chernoff bound and application to community detection in the stochastic block models, Community detection in the sparse hypergraph stochastic block model, Learning sparse graphons and the generalized Kesten-Stigum threshold, Unnamed Item, Unnamed Item, Eigenvalues of the non-backtracking operator detached from the bulk

Cites Work

• Unnamed Item
• Unnamed Item
• Impact of regularization on spectral clustering
• Community detection in sparse networks via Grothendieck's inequality
• Small subgraphs of random regular graphs
• Ramanujan graphs
• On the second eigenvalue of a graph
• A proof of the block model threshold conjecture
• Group synchronization on grids
• Fundamental limits of weak recovery with applications to phase retrieval
• Spectral redemption in clustering sparse networks
• Phase transitions in semidefinite relaxations
• Expander graphs and their applications
• Graph Partitioning via Adaptive Spectral Techniques
• A proof of alon's second eigenvalue conjecture
• Random Geometric Graphs
• Community Detection and Stochastic Block Models
• Proof of the Achievability Conjectures for the General Stochastic Block Model
• A Simple SVD Algorithm for Finding Hidden Partitions
• Robust Estimators in High-Dimensions Without the Computational Intractability
• Faster Algorithms via Approximation Theory
• From Frequency to Meaning: Vector Space Models of Semantics
• Mixture models, robustness, and sum of squares proofs
• Robust moment estimation and improved clustering via sum of squares
• Community detection thresholds and the weak Ramanujan property
• Semidefinite programs on sparse random graphs and their application to community detection
• How robust are reconstruction thresholds for community detection?
• Large Deviations for the Graph Distance in Supercritical Continuum Percolation
• Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator
• The Rotation of Eigenvectors by a Perturbation. III
• Graph Sparsification by Effective Resistances