Optimization via low-rank approximation for community detection in networks

DOI10.1214/15-AOS1360zbMath1331.62312arXiv1406.0067OpenAlexW2964176492MaRDI QIDQ5963526

Can M. Le, R. V. Vershinin, Elizaveta Levina

Publication date: 22 February 2016

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

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

zbMATH Keywords

social networkscommunity detectionspectral clusteringstochastic block model

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Asymptotic properties of nonparametric inference (62G20) Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Related Items

Consistency of modularity clustering on random geometric graphs, Model assisted variable clustering: minimax-optimal recovery and algorithms, Convexified modularity maximization for degree-corrected stochastic block models, Hybrid Kronecker Product Decomposition and Approximation, Clustering heterogeneous financial networks, Unnamed Item, Optimization via low-rank approximation for community detection in networks, The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics, Detecting Overlapping Communities in Networks Using Spectral Methods

Uses Software

• Tabu search
• Minksum

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pseudo-likelihood methods for community detection in large sparse networks
• Fast community detection by SCORE
• Belief propagation, robust reconstruction and optimal recovery of block models
• Spectral clustering and the high-dimensional stochastic blockmodel
• Uncovering latent structure in valued graphs: a variational approach
• Estimation and prediction for stochastic blockmodels for graphs with latent block structure
• Connected components in random graphs with given expected degree sequences
• Consistency of community detection in networks under degree-corrected stochastic block models
• Consistency of spectral clustering in stochastic block models
• Role of normalization in spectral clustering for stochastic blockmodels
• From the zonotope construction to the Minkowski addition of convex polytopes
• A nonparametric view of network models and Newman–Girvan and other modularities
• Mixed membership stochastic blockmodels
• Estimation and Prediction for Stochastic Blockstructures
• Latent Space Approaches to Social Network Analysis
• Community structure in social and biological networks
• First-principles multiway spectral partitioning of graphs
• Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
• A Survey of Statistical Network Models
• Community detection thresholds and the weak Ramanujan property
• Concentration and regularization of random graphs
• A Cheeger Inequality for the Graph Connection Laplacian
• Optimization via low-rank approximation for community detection in networks