Optimization via low-rank approximation for community detection in networks
From MaRDI portal
Publication:5963526
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.
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
Cites work
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- scientific article; zbMATH DE number 1302201 (Why is no real title available?)
- scientific article; zbMATH DE number 2019639 (Why is no real title available?)
- scientific article; zbMATH DE number 2100602 (Why is no real title available?)
- A Cheeger Inequality for the Graph Connection Laplacian
- A nonparametric view of network models and Newman–Girvan and other modularities
- A survey of statistical network models
- Belief propagation, robust reconstruction and optimal recovery of block models
- Community detection thresholds and the weak Ramanujan property
- Community structure in social and biological networks
- Concentration and regularization of random graphs
- 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
- Estimation and Prediction for Stochastic Blockstructures
- Estimation and prediction for stochastic blockmodels for graphs with latent block structure
- Fast community detection by SCORE
- First-principles multiway spectral partitioning of graphs
- From the zonotope construction to the Minkowski addition of convex polytopes
- Latent Space Approaches to Social Network Analysis
- Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
- Mixed membership stochastic blockmodels
- Optimization via low-rank approximation for community detection in networks
- Pseudo-likelihood methods for community detection in large sparse networks
- Role of normalization in spectral clustering for stochastic blockmodels
- Spectral clustering and the high-dimensional stochastic blockmodel
- Uncovering latent structure in valued graphs: a variational approach
Cited in
(13)- Convexified modularity maximization for degree-corrected stochastic block models
- Local network community detection with continuous optimization of conductance and weighted kernel k-means
- Model assisted variable clustering: minimax-optimal recovery and algorithms
- Variational community partition with novel network structure centrality prior
- Consistency of modularity clustering on random geometric graphs
- Optimization via low-rank approximation for community detection in networks
- Efficient split likelihood-based method for community detection of large-scale networks
- Clustering heterogeneous financial networks
- Hybrid Kronecker Product Decomposition and Approximation
- scientific article; zbMATH DE number 7626745 (Why is no real title available?)
- Fast cluster detection in networks by first order optimization
- Detecting overlapping communities in networks using spectral methods
- The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics
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)
