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
(52)- Improvements on SCORE, especially for weak signals
- Mixed Membership Estimation for Social Networks
- The (un)supervised NMF methods for discovering overlapping communities as well as hubs and outliers in networks
- Overlapping community detection using a generative model for networks
- Social network community detection using agglomerative spectral clustering
- SONIC: streaming overlapping community detection
- Optimal adaptivity of signed-polygon statistics for network testing
- Overlapping community detection in networks via sparse spectral decomposition
- Edgeworth expansions for network moments
- Identifiability and parameter estimation of the overlapped stochastic co-block model
- Mixed membership stochastic blockmodels for heterogeneous networks
- Detection of disjoint or overlapping communities in networks
- A tensor approach to learning mixed membership community models
- Spectral redemption in clustering sparse networks
- Non-parametric overlapping community detection
- Learning overlapping communities in complex networks via non-negative matrix factorization
- Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM)
- scientific article; zbMATH DE number 7307464 (Why is no real title available?)
- Inference for multiple heterogeneous networks with a common invariant subspace
- Discovering overlapping communities in social networks: a novel game-theoretic approach
- Efficient discovery of overlapping communities in massive networks
- Overlapping community detection in networks
- Estimating Mixed Memberships With Sharp Eigenvector Deviations
- Hierarchical Community Detection by Recursive Partitioning
- Asymptotic Theory of Eigenvectors for Random Matrices With Diverging Spikes
- Estimating mixed-memberships using the symmetric Laplacian inverse matrix
- Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
- Latent Space Model for Higher-Order Networks and Generalized Tensor Decomposition
- Special invited paper: the SCORE normalization, especially for heterogeneous network and text data
- Survival Mixed Membership Blockmodel
- Community detection in complex networks: from statistical foundations to data science applications
- Co-citation and Co-authorship Networks of Statisticians
- 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
- Clique and cycle frequencies in a sparse random graph model with overlapping communities
- Applications of dual regularized Laplacian matrix for community detection
- Aggregate spectral clustering for community detection in multi-layer popularity adjusted block model
- Degree-Heterogeneous Latent Class Analysis for High-Dimensional Discrete Data
- A pseudo-likelihood approach to community detection in weighted networks
- Network Goodness-of-Fit for the Block-Model Family
- Joint Spectral Clustering in Multilayer Degree-Corrected Stochastic Blockmodels
- Overlapping community detection in weighted networks
- Exact recovery discrimination in planted bisection model
- Optimal Network Membership Estimation under Severe Degree Heterogeneity
- Curvature-based clustering on graphs
- Estimating network-mediated causal effects via principal components network regression
- An overview of asymptotic normality in stochastic blockmodels: cluster analysis and inference
- Regularized spectral clustering in overlapping networks
- SAT-based models for overlapping community detection in networks
- Estimating the number of communities by spectral methods
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)
