Fast community detection by SCORE

Abstract

Consider a network where the nodes split into $K$ different communities. The community labels for the nodes are unknown and it is of major interest to estimate them (i.e., community detection). Degree Corrected Block Model (DCBM) is a popular network model. How to detect communities with the DCBM is an interesting problem, where the main challenge lies in the degree heterogeneity. We propose a new approach to community detection which we call the Spectral Clustering On Ratios-of-Eigenvectors (SCORE). Compared to classical spectral methods, the main innovation is to use the entry-wise ratios between the first leading eigenvector and each of the other leading eigenvectors for clustering. Let $A$ be the adjacency matrix of the network. We first obtain the $K$ leading eigenvectors of $A$, say, ${\hat{\eta }}_1,\dots ,{\hat{\eta }}_K$, and let $\hat{R}$ be the $n\times (K-1)$ matrix such that $\hat{R}(i,k)={\hat{\eta }}_{k+1}(i)/{\hat{\eta }}_1(i)$, $1\le i\le n$, $1\le k\le K-1$. We then use $\hat{R}$ for clustering by applying the $k$-means method. The central surprise is, the effect of degree heterogeneity is largely ancillary, and can be effectively removed by taking entry-wise ratios between ${\hat{\eta }}_{k+1}$ and ${\hat{\eta }}_1$, $1\le k\le K-1$. The method is successfully applied to the web blogs data and the karate club data, with error rates of $58/1222$ and $1/34$, respectively. These results are more satisfactory than those by the classical spectral methods. Additionally, compared to modularity methods, SCORE is easier to implement, computationally faster, and also has smaller error rates. We develop a theoretic framework where we show that under mild conditions, the SCORE stably yields consistent community detection. In the core of the analysis is the recent development on Random Matrix Theory (RMT), where the matrix-form Bernstein inequality is especially helpful.

Published in at http://dx.doi.org/10.1214/14-AOS1265 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (9)

• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Stochastic blockmodels and community structure in networks
• Spectral redemption: clustering sparse networks
• Fast community detection by SCORE
• Pseudo-likelihood methods for community detection in large sparse networks
• Modeling homophily and stochastic equivalence in symmetric relational data
• Model Selection for Degree-corrected Block Models

Cited by in corpus (105)

• Consistency of spectral clustering in stochastic block models
• Fast community detection by SCORE
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
• Coauthorship and Citation Networks for Statisticians
• A goodness-of-fit test for stochastic block models
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Exponential-Family Models of Random Graphs: Inference in Finite-, Super-, and Infinite Population Scenarios
• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• Achieving Optimal Misclassification Proportion in Stochastic Block Model
• A Survey on Theoretical Advances of Community Detection in Networks
• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• Statistical Modelling of Citation Exchange Between Statistics Journals
• Testing for Global Network Structure Using Small Subgraph Statistics
• Mixed Membership Estimation for Social Networks
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Embedding-based Silhouette Community Detection
• Spectral Clustering for Multiple Sparse Networks: I
• A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models
• Determining the Number of Communities in Degree-corrected Stochastic Block Models
• Inference via Message Passing on Partially Labeled Stochastic Block Models
• Anomaly Detection in Networks with Application to Financial Transaction Networks
• Improvements on SCORE, Especially for Weak Signals
• Consistent structure estimation of exponential-family random graph models with block structure
• Network cross-validation by edge sampling
• Community detection by spectral methods in multi-layer networks
• Community Detection in Degree-Corrected Block Models
• Community detection with nodal information
• Regularized spectral methods for clustering signed networks
• Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis
• Spectral Algorithms for Community Detection in Directed Networks
• Community detection for weighted bipartite networks
• Network Representation Using Graph Root Distributions
• General Community Detection with Optimal Recovery Conditions for Multi-relational Sparse Networks with Dependent Layers
• Exploration of Large Networks with Covariates via Fast and Universal Latent Space Model Fitting
• The blessing of transitivity in sparse and stochastic networks
• Robust high dimensional factor models with applications to statistical machine learning
• Recent Advances in Text Analysis
• Network Cross-Validation for Determining the Number of Communities in Network Data
• A unified framework for spectral clustering in sparse graphs
• A generalized hypothesis test for community structure in networks
• Orthogonal symmetric non-negative matrix factorization under the stochastic block model
• A Sharp Lower Bound for Mixed-membership Estimation
• Consistency of Spectral Clustering on Hierarchical Stochastic Block Models
• Estimating whole brain dynamics using spectral clustering
• State Aggregation Learning from Markov Transition Data
• Pairwise Covariates-adjusted Block Model for Community Detection
• Spectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel
• Profile Likelihood Biclustering
• Higher-Order Spectral Clustering under Superimposed Stochastic Block Model
• A useful criterion on studying consistent estimation in community detection
• Detecting Latent Communities in Network Formation Models
• How Many Communities Are There?
• Influential Feature PCA for high dimensional clustering
• Spectral clustering via adaptive layer aggregation for multi-layer networks
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• Linear regression and its inference on noisy network-linked data
• Spectral clustering in the dynamic stochastic block model
• Estimating the number of communities in weighted networks
• Using Maximum Entry-Wise Deviation to Test the Goodness-of-Fit for Stochastic Block Models
• Graph clustering with Boltzmann machines
• Community models for networks observed through edge nominations
• Testing Degree Corrections in Stochastic Block Models
• Community Detection Based on the $L_{\infty }$ convergence of eigenvectors in DCBM
• Informative core identification in complex networks
• Community Detection in General Hypergraph via Graph Embedding
• An Annotated Graph Model with Differential Degree Heterogeneity for Directed Networks
• SCOREH+: A High-Order Node Proximity Spectral Clustering on Ratios-of-Eigenvectors Algorithm for Community Detection
• Directed mixed membership stochastic blockmodel
• Reproducible Science with LaTeX
• Directed degree corrected mixed membership model and estimating community memberships in directed networks
• Distributed Community Detection for Large Scale Networks Using Stochastic Block Model
• Graph Clustering Via QUBO and Digital Annealing
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian
• Root and community inference on the latent growth process of a network
• Asymptotic adaptive threshold for connectivity in a random geometric social network
• A Time-Varying Network for Cryptocurrencies
• Dual regularized Laplacian spectral clustering methods on community detection
• Perturbation of linear forms of singular vectors under Gaussian noise
• Graph matching beyond perfectly-overlapping Erdős--Rényi random graphs
• Community Detection by Principal Components Clustering Methods
• Distributed Pseudo-Likelihood Method for Community Detection in Large-Scale Networks
• Automatic hermiticity for mixed states
• A Sparse Completely Positive Relaxation of the Modularity Maximization for Community Detection
• Impact of regularization on spectral clustering under the mixed membership stochastic block model
• On role extraction for digraphs via neighbourhood pattern similarity
• An improved spectral clustering method for community detection under the degree-corrected stochastic blockmodel
• Overlapping community detection in networks via sparse spectral decomposition
• An improved spectral clustering method for mixed membership community detection
• The Interplay of Demographic Variables and Social Distancing Scores in Deep Prediction of U.S. COVID-19 Cases
• Consistent Spectral Clustering of Network Block Models under Local Differential Privacy
• A Geometrical Approach to Topic Model Estimation
• Consistency of regularized spectral clustering in degree-corrected mixed membership model
• Semi-supervised learning in unbalanced and heterogeneous networks
• Community Detection by $L_0$-penalized Graph Laplacian
• Consistent model selection for the Degree Corrected Stochastic Blockmodel
• Multi-view Banded Spectral Clustering with Application to ICD9 Clustering
• Localized geometry detection in scale-free random graphs
• Co-factor analysis of citation networks
• A Unified Framework for Community Detection and Model Selection in Blockmodels
• Overlapping community detection in weighted networks
• A two-stage working model strategy for network analysis under Hierarchical Exponential Random Graph Models
• Outliers Detection in Networks with Missing Links
• Overlapping and nonoverlapping models
• Individual-centered partial information in social networks
• Mixed-SCORE+ for mixed membership community detection