Community detection in sparse networks via Grothendieck's inequality

DOI10.1007/s00440-015-0659-zzbMath1357.90111arXiv1411.4686OpenAlexW2963105348WikidataQ105583375 ScholiaQ105583375MaRDI QIDQ737326

Olivier Guédon, R. V. Vershinin

Publication date: 10 August 2016

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

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

zbMATH Keywords

sparse networksGrothendieck inequalitysemidefinite optimization problems

Mathematics Subject Classification ID

Semidefinite programming (90C22) Integer programming (90C10) Stochastic network models in operations research (90B15) Combinatorial probability (60C05)

Related Items

Edgeworth expansions for network moments, Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information, Optimal Bipartite Network Clustering, Information-theoretic thresholds from the cavity method, Unnamed Item, A review of dynamic network models with latent variables, Local law and Tracy-Widom limit for sparse stochastic block models, Model assisted variable clustering: minimax-optimal recovery and algorithms, Rate optimal Chernoff bound and application to community detection in the stochastic block models, Convexified modularity maximization for degree-corrected stochastic block models, Graphon estimation via nearest‐neighbour algorithm and two‐dimensional fused‐lasso denoising, Community detection in the sparse hypergraph stochastic block model, Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates, Unnamed Item, Mean estimation with sub-Gaussian rates in polynomial time, Entrywise eigenvector analysis of random matrices with low expected rank, A Spectral Method for Joint Community Detection and Orthogonal Group Synchronization, Phase transitions in semidefinite relaxations, Semidefinite programming based community detection for node-attributed networks and multiplex networks, Asymptotic uncertainty quantification for communities in sparse planted bi-section models, Central limit theorems for global and local empirical measures of diffusions on Erdős-Rényi graphs, Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks, Clustering heterogeneous financial networks, Clustering subgaussian mixtures by semidefinite programming, Theoretical and computational guarantees of mean field variational inference for community detection, Embedding-based silhouette community detection, Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery, Thin-shell concentration for random vectors in Orlicz balls via moderate deviations and Gibbs measures, Unnamed Item, On semidefinite relaxations for the block model, Community Detection and Stochastic Block Models, A Sparse Completely Positive Relaxation of the Modularity Maximization for Community Detection, Convex relaxation methods for community detection, Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees, Convex optimization for the densest subgraph and densest submatrix problems, Community detection in sparse networks via Grothendieck's inequality, Profile likelihood biclustering, Sequential subspace change point detection, Optimal graphon estimation in cut distance, Partial recovery bounds for clustering with the relaxed \(K\)-means, Interacting diffusions on random graphs with diverging average degrees: hydrodynamics and large deviations, Covariate Regularized Community Detection in Sparse Graphs, Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model, The large deviation principle for interacting dynamical systems on random graphs, Graph Powering and Spectral Robustness, Long time dynamics for interacting oscillators on graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pseudo-likelihood methods for community detection in large sparse networks
• Consistency thresholds for the planted bisection model
• Impact of regularization on spectral clustering
• Belief propagation, robust reconstruction and optimal recovery of block models
• Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels
• Localization and delocalization of eigenvectors for heavy-tailed random matrices
• Probability in Banach spaces. Isoperimetry and processes
• Spectral clustering and the high-dimensional stochastic blockmodel
• Nuclear norm minimization for the planted clique and biclique problems
• Community detection in sparse networks via Grothendieck's inequality
• Estimation and prediction for stochastic blockmodels for graphs with latent block structure
• A proof of the block model threshold conjecture
• On semidefinite relaxations for the block model
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Consistency of maximum-likelihood and variational estimators in the stochastic block model
• Consistency of spectral clustering in stochastic block models
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices
• Grothendieck-Type Inequalities in Combinatorial Optimization
• A nonparametric view of network models and Newman–Girvan and other modularities
• The solution of some random NP-hard problems in polynomial expected time
• Mixed membership stochastic blockmodels
• Graph Partitioning via Adaptive Spectral Techniques
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• Semidefinite relaxation and nonconvex quadratic optimization
• Proof of the Achievability Conjectures for the General Stochastic Block Model
• Community detection thresholds and the weak Ramanujan property
• The phase transition in inhomogeneous random graphs
• Spectral techniques applied to sparse random graphs
• Exploring complex networks
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• Semidefinite programs on sparse random graphs and their application to community detection
• Concentration and regularization of random graphs
• Singular vectors under random perturbation
• Grothendieck’s Theorem, past and present
• Approximating the Cut-Norm via Grothendieck's Inequality
• The Grothendieck Constant is Strictly Smaller than Krivine's Bound
• Absolutely summing operators in $ℒ_{p}$-spaces and their applications
• The Rotation of Eigenvectors by a Perturbation. III