Community Detection and Stochastic Block Models

zbMath1403.62110arXiv1703.10146MaRDI QIDQ4558502

Emmanuel Abbe

Publication date: 22 November 2018

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

zbMATH Keywords

clusteringrandom graphsunsupervised learningspectral algorithmscommunity detectionstochastic block modelsnetwork data analysiscomputational gaps

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Random graphs (graph-theoretic aspects) (05C80) Research exposition (monographs, survey articles) pertaining to statistics (62-02)

Related Items

Testing community structure for hypergraphs, Bayesian testing for exogenous partition structures in stochastic block models, Community detection for weighted networks with unknown number of communities, A likelihood-ratio type test for stochastic block models with bounded degrees, Maximum A Posteriori Inference of Random Dot Product Graphs via Conic Programming, Edgeworth expansions for network moments, Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral estimator, A PROBABILISTIC FRIENDSHIP NETWORK MODEL, Assortativity and bidegree distributions on Bernoulli random graph superpositions, Optimal Bipartite Network Clustering, Community detection with a subsampled semidefinite program, Hurdle Blockmodels for Sparse Network Modeling, Randomized Spectral Clustering in Large-Scale Stochastic Block Models, Loop-erased partitioning of a graph: mean-field analysis, Cut norm discontinuity of triangular truncation of graphons, Strong replica symmetry in high-dimensional optimal Bayesian inference, Identifiability and parameter estimation of the overlapped stochastic co-block model, Post-processing partitions to identify domains of modularity optimization, When is sync globally stable in sparse networks of identical Kuramoto oscillators?, Unnamed Item, Unnamed Item, Test dense subgraphs in sparse uniform hypergraph, Estimation of low-rank matrices via approximate message passing, A noncommutative approach to the graphon Fourier transform, An information-percolation bound for spin synchronization on general graphs, A threshold for cutoff in two-community random graphs, Higher-order spectral clustering for geometric graphs, A FastMap-based algorithm for block modeling, Local law and Tracy-Widom limit for sparse stochastic block models, Optimal rates for community estimation in the weighted stochastic block model, Spectral properties for the Laplacian of a generalized Wigner matrix, Mean isoperimetry with control on outliers: exact and approximation algorithms, Joint Community Detection and Rotational Synchronization via Semidefinite Programming, Find Your Place: Simple Distributed Algorithms for Community Detection, Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering, Unnamed Item, Unnamed Item, Unnamed Item, Entrywise eigenvector analysis of random matrices with low expected rank, Graph convolutional neural networks via scattering, Total Variation Based Community Detection Using a Nonlinear Optimization Approach, Singular value distribution of dense random matrices with block Markovian dependence, Phase transitions in finite random networks, Non-backtracking spectra of weighted inhomogeneous random graphs, Classification on Large Networks: A Quantitative Bound via Motifs and Graphons (Research), Step-by-step community detection in volume-regular graphs, Estimating a network from multiple noisy realizations, Mixed-case community detection problem in social networks: algorithms and analysis, Notes on computational-to-statistical gaps: predictions using statistical physics, Uniform Bounds for Invariant Subspace Perturbations, Outlier detection in networks with missing links, Unnamed Item, Unnamed Item, Contiguity and non-reconstruction results for planted partition models: the dense case, Charting the replica symmetric phase, Towards optimal estimation of bivariate isotonic matrices with unknown permutations, Spin systems on Bethe lattices, Generating directed networks with predetermined assortativity measures, Estimating the number of communities by spectral methods, Adjusted chi-square test for degree-corrected block models, Unnamed Item, Unnamed Item, Convex relaxation methods for community detection, Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing, Robust high-dimensional factor models with applications to statistical machine learning, Nonreconstruction of high-dimensional stochastic block model with bounded degree, Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees, Detecting a planted community in an inhomogeneous random graph, Profile likelihood biclustering, On the estimation of latent distances using graph distances, Collective dynamics of opposing groups with stochastic communication, Exact recovery in the hypergraph stochastic block model: a spectral algorithm, Exact recovery in the Ising blockmodel, The overlap gap property in principal submatrix recovery, On the computational tractability of statistical estimation on amenable graphs, Spectral clustering revisited: information hidden in the Fiedler vector, Group synchronization on grids, Partial recovery bounds for clustering with the relaxed \(K\)-means, Estimation of dense stochastic block models visited by random walks, An infinite-dimensional metapopulation SIS model, The planted matching problem: phase transitions and exact results, Public health interventions in the face of pandemics: network structure, social distancing, and heterogeneity, Testing degree corrections in stochastic block models, Extended stochastic block models with application to criminal networks, The Interplay of Demographic Variables and Social Distancing Scores in Deep Prediction of U.S. COVID-19 Cases, Diffusion State Distances: Multitemporal Analysis, Fast Algorithms, and Applications to Biological Networks, Statistical limits of sparse mixture detection, Clustering for epidemics on networks: A geometric approach, Sharp optimal recovery in the two component Gaussian mixture model, An \({\ell_p}\) theory of PCA and spectral clustering, Hamiltonicity of Random Graphs in the Stochastic Block Model, Unnamed Item, Unnamed Item, Unnamed Item, Robust group synchronization via cycle-edge message passing, Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials, Global and individualized community detection in inhomogeneous multilayer networks, Relating Modularity Maximization and Stochastic Block Models in Multilayer Networks, Blind Identification of Stochastic Block Models from Dynamical Observations, Compressive Sensing for Cut Improvement and Local Clustering, Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance, Hierarchical Community Detection by Recursive Partitioning, Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes, Graph Neural Networks for Natural Language Processing: A Survey, Modularity Maximization for Graphons, Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis, Core-periphery models via integer programming: maximizing the influence of the core, \(k\)-median: exact recovery in the extended stochastic ball model, Optimal hierarchical clustering on a graph, Community informed experimental design, Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models, Community detection in the sparse hypergraph stochastic block model, Clustering and percolation on superpositions of Bernoulli random graphs, A distributed community detection algorithm for large scale networks under stochastic block models, Nonbacktracking Spectral Clustering of Nonuniform Hypergraphs, Poisson degree corrected dynamic stochastic block model, Prediction models with graph kernel regularization for network data, Fast Network Community Detection With Profile-Pseudo Likelihood Methods, On the chromatic number in the stochastic block model, Community detection for multilayer weighted networks, Bayesian learning of graph substructures, Universal rank inference via residual subsampling with application to large networks, On the limiting spectral distributions of stochastic block models, A survey on model-based co-clustering: high dimension and estimation challenges, Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models, Graph sequences sampled from Robinson graphons, Entropic Optimal Transport on Random Graphs, A practical two-sample test for weighted random graphs, Estimating mixed-memberships using the symmetric Laplacian inverse matrix, Metastability of the Potts ferromagnet on random regular graphs, Local laws for multiplication of random matrices, Euclidean Representation of Low-Rank Matrices and Its Geometric Properties, Subnetwork estimation for spatial autoregressive models in large-scale networks, Asymptotic uncertainty quantification for communities in sparse planted bi-section models, Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method, Learning sparse graphons and the generalized Kesten-Stigum threshold, Community structure recovery and interaction probability estimation for gossip opinion dynamics, Entrywise limit theorems for eigenvectors of signal-plus-noise matrix models with weak signals, Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks, Community Detection in Censored Hypergraph, Spectral Estimation of Large Stochastic Blockmodels with Discrete Nodal Covariates, Limiting spectral distribution of stochastic block model, How social networks influence human behavior: an integrated latent space approach for differential social influence, The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime, The Ising Antiferromagnet and Max Cut on Random Regular Graphs, Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• Fast community detection by SCORE
• Belief propagation, robust reconstruction and optimal recovery of block models
• Optimal detection of sparse principal components in high dimension
• Reconstruction and estimation in the planted partition model
• Community detection in sparse networks via Grothendieck's inequality
• Reconstruction on trees and spin glass transition
• Limits of dense graph sequences
• Spectral partitioning works: planar graphs and finite element meshes
• Finding one community in a sparse graph
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Representations for partially exchangeable arrays of random variables
• Estimation and prediction for stochastic blockmodels for graphs with latent block structure
• Information flow on trees
• On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice.
• Information-theoretic thresholds from the cavity method
• A spectral algorithm with additive clustering for the recovery of overlapping communities in networks
• On semidefinite relaxations for the block model
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Random Laplacian matrices and convex relaxations
• Broadcasting on trees and the Ising model.
• Robust reconstruction on trees is determined by the second eigenvalue.
• Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Stochastic blockmodels with a growing number of classes
• A nonparametric view of network models and Newman–Girvan and other modularities
• Spectral redemption in clustering sparse networks
• Phase transitions in semidefinite relaxations
• Information Recovery From Pairwise Measurements
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
• Exact Recovery in the Stochastic Block Model
• The solution of some random NP-hard problems in polynomial expected time
• Mixed membership stochastic blockmodels
• Mutual Information and Minimum Mean-Square Error in Gaussian Channels
• Graph Partitioning via Adaptive Spectral Techniques
• A proof of alon's second eigenvalue conjecture
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Random graph models of social networks
• Community structure in social and biological networks
• Proof of the Achievability Conjectures for the General Stochastic Block Model
• Asymptotic mutual information for the balanced binary stochastic block model
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Efficient discovery of overlapping communities in massive networks
• A Survey of Statistical Network Models
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• The phase transition in inhomogeneous random graphs
• Spectral techniques applied to sparse random graphs
• Semidefinite programs on sparse random graphs and their application to community detection
• How robust are reconstruction thresholds for community detection?
• Information Limits for Recovering a Hidden Community
• A Polylogarithmic Approximation of the Minimum Bisection
• Understanding Machine Learning
• A Limit Theorem for Multidimensional Galton-Watson Processes
• Spectral norm of random matrices
• Networks
• The two possible values of the chromatic number of a random graph