Optimization via low-rank approximation for community detection in networks

DOI10.1214/15-AOS1360zbMATH Open1331.62312arXiv1406.0067OpenAlexW2964176492MaRDI QIDQ5963526FDOQ5963526

Can M. Le, Roman Vershynin, Elizaveta Levina

Publication date: 22 February 2016

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

Abstract: Community detection is one of the fundamental problems of network analysis, for which a number of methods have been proposed. Most model-based or criteria-based methods have to solve an optimization problem over a discrete set of labels to find communities, which is computationally infeasible. Some fast spectral algorithms have been proposed for specific methods or models, but only on a case-by-case basis. Here we propose a general approach for maximizing a function of a network adjacency matrix over discrete labels by projecting the set of labels onto a subspace approximating the leading eigenvectors of the expected adjacency matrix. This projection onto a low-dimensional space makes the feasible set of labels much smaller and the optimization problem much easier. We prove a general result about this method and show how to apply it to several previously proposed community detection criteria, establishing its consistency for label estimation in each case and demonstrating the fundamental connection between spectral properties of the network and various model-based approaches to community detection. Simulations and applications to real-world data are included to demonstrate our method performs well for multiple problems over a wide range of parameters.

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

zbMATH Keywords

stochastic block modelcommunity detectionsocial networksspectral clustering

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

• Optimization via low-rank approximation for community detection in networks
• Hybrid Kronecker Product Decomposition and Approximation
• Consistency of modularity clustering on random geometric graphs
• Convexified modularity maximization for degree-corrected stochastic block models
• The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
• Clustering heterogeneous financial networks
• Model assisted variable clustering: minimax-optimal recovery and algorithms
• Title not available (Why is that?)
• Detecting Overlapping Communities in Networks Using Spectral Methods
• Efficient split likelihood-based method for community detection of large-scale networks

Uses Software

• Tabu search
• Minksum

   Recommendations

• Community detection via an efficient nonconvex optimization approach based on modularity 👍 👎
• Community detection with a subsampled semidefinite program 👍 👎
• Community detection by \(L_{0}\)-penalized graph Laplacian 👍 👎
• Convex relaxation methods for community detection 👍 👎
• Searching Graph Communities by Modularity Maximization via Convex Optimization 👍 👎
• Community detection based on significance optimization in complex networks 👍 👎
• Total Variation Based Community Detection Using a Nonlinear Optimization Approach 👍 👎
• Community detection in sparse random networks 👍 👎

This page was built for publication: Optimization via low-rank approximation for community detection in networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963526)