Detecting overlapping communities in networks using spectral methods
From MaRDI portal
Abstract: Community detection is a fundamental problem in network analysis which is made more challenging by overlaps between communities which often occur in practice. Here we propose a general, flexible, and interpretable generative model for overlapping communities, which can be thought of as a generalization of the degree-corrected stochastic block model. We develop an efficient spectral algorithm for estimating the community memberships, which deals with the overlaps by employing the K-medians algorithm rather than the usual K-means for clustering in the spectral domain. We show that the algorithm is asymptotically consistent when networks are not too sparse and the overlaps between communities not too large. Numerical experiments on both simulated networks and many real social networks demonstrate that our method performs very well compared to a number of benchmark methods for overlapping community detection.
Recommendations
Cites work
- A nonparametric view of network models and Newman–Girvan and other modularities
- A survey of statistical network models
- A tensor approach to learning mixed membership community models
- An Exponential Family of Probability Distributions for Directed Graphs
- Community detection in degree-corrected block models
- Community discovery using nonnegative matrix factorization
- Consistency of community detection in networks under degree-corrected stochastic block models
- Convexified modularity maximization for degree-corrected stochastic block models
- Fast community detection by SCORE
- Finding overlapping communities in networks by label propagation
- Generalized random dot product graph
- Graph partitioning models for parallel computing
- Hypothesis testing for automated community detection in networks
- Impact of regularization on spectral clustering
- Limit theorems for eigenvectors of the normalized Laplacian for random graphs
- Minimax rates of community detection in stochastic block models
- Mixed membership stochastic blockmodels
- Model selection in overlapping stochastic block models
- Network cross-validation by edge sampling
- Network cross-validation for determining the number of communities in network data
- Optimization via low-rank approximation for community detection in networks
- Overlapping community detection in networks
- Protein interaction networks. Computational analysis.
- Pseudo-likelihood methods for community detection in large sparse networks
- Random Dot Product Graph Models for Social Networks
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
- Role of normalization in spectral clustering for stochastic blockmodels
- Semidefinite programming based preconditioning for more robust near-separable nonnegative matrix factorization
- Spectral clustering and the high-dimensional stochastic blockmodel
- Stochastic blockmodels with a growing number of classes
Cited in
(50)- Co-citation and Co-authorship Networks of Statisticians
- Exact recovery discrimination in planted bisection model
- Optimal Network Membership Estimation under Severe Degree Heterogeneity
- Survival Mixed Membership Blockmodel
- SONIC: streaming overlapping community detection
- Curvature-based clustering on graphs
- Estimating network-mediated causal effects via principal components network regression
- The (un)supervised NMF methods for discovering overlapping communities as well as hubs and outliers in networks
- Overlapping community detection in networks via sparse spectral decomposition
- Detection of disjoint or overlapping communities in networks
- Optimal adaptivity of signed-polygon statistics for network testing
- Overlapping community detection in networks
- A tensor approach to learning mixed membership community models
- Estimating mixed-memberships using the symmetric Laplacian inverse matrix
- Efficient discovery of overlapping communities in massive networks
- Edgeworth expansions for network moments
- Spectral redemption in clustering sparse networks
- Community detection in complex networks: from statistical foundations to data science applications
- Clique and cycle frequencies in a sparse random graph model with overlapping communities
- Learning overlapping communities in complex networks via non-negative matrix factorization
- Non-parametric overlapping community detection
- SAT-based models for overlapping community detection in networks
- Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
- Latent Space Model for Higher-Order Networks and Generalized Tensor Decomposition
- Identifiability and parameter estimation of the overlapped stochastic co-block model
- Mixed membership stochastic blockmodels for heterogeneous networks
- Discussion of “Cocitation and Coauthorship Networks of Statisticians”
- Rejoinder: “Co-citation and Co-authorship Networks of Statisticians”
- Hierarchical overlapping community detection for weighted networks
- Tractably modelling dependence in networks beyond exchangeability
- Aggregate spectral clustering for community detection in multi-layer popularity adjusted block model
- Overlapping community detection using a generative model for networks
- An overview of asymptotic normality in stochastic blockmodels: cluster analysis and inference
- Joint Spectral Clustering in Multilayer Degree-Corrected Stochastic Blockmodels
- Estimating Mixed Memberships With Sharp Eigenvector Deviations
- Degree-Heterogeneous Latent Class Analysis for High-Dimensional Discrete Data
- Estimating the number of communities by spectral methods
- A pseudo-likelihood approach to community detection in weighted networks
- Applications of dual regularized Laplacian matrix for community detection
- Network Goodness-of-Fit for the Block-Model Family
- Improvements on SCORE, especially for weak signals
- Mixed Membership Estimation for Social Networks
- Overlapping community detection in weighted networks
- scientific article; zbMATH DE number 7415085 (Why is no real title available?)
- Hierarchical Community Detection by Recursive Partitioning
- scientific article; zbMATH DE number 7307464 (Why is no real title available?)
- Social network community detection using agglomerative spectral clustering
- Special invited paper: the SCORE normalization, especially for heterogeneous network and text data
- Discovering overlapping communities in social networks: a novel game-theoretic approach
- Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes
This page was built for publication: Detecting overlapping communities in networks using spectral methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5027027)
