Fast community detection by SCORE

DOI10.48550/ARXIV.1211.5803zbMATH Open1310.62076arXiv1211.5803OpenAlexW2027966435MaRDI QIDQ144808FDOQ144808

Authors: Jiashun Jin, Jiashun Jin 

Publication date: 25 November 2012

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

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,ldots,hat{eta}_K$, and let $hatR$ be the $nimes(K-1)$ matrix such that $hatR(i,k)=hat{eta}_{k+1}(i)/hat{eta}_1(i)$, $1leqileqn$, $1leqkleqK-1$. We then use $hatR$ 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$, $1leqkleqK-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.

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

Recommendations

• scientific article; zbMATH DE number 6962251
• Fast unfolding of communities in large networks
• FAST COMMUNITY IDENTIFICATION BY HIERARCHICAL GROWTH
• Fast Network Community Detection With Profile-Pseudo Likelihood Methods
• Fast community detection in complex networks with a \(K\)-depths classifier
• Detecting Community Structure by Network Vectorization
• Algorithms and Models for the Web-Graph

zbMATH Keywords

community detectionHamming distancePCAsparsitysocial networkspectral analysis\(k\)-means methoddegree corrected block model (DCBM)moderate deviationmodularity

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Applications of statistics to social sciences (62P25) Clustering in the social and behavioral sciences (91C20) Social networks; opinion dynamics (91D30)

Cites Work

• The elements of statistical learning. Data mining, inference, and prediction
• A nonparametric view of network models and Newman–Girvan and other modularities
• Matrix Analysis
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• Spectral clustering and the high-dimensional stochastic blockmodel
• Pseudo-likelihood methods for community detection in large sparse networks
• A survey of statistical network models
• Title not available (Why is that?)
• Title not available (Why is that?)
• Statistical analysis of network data. Methods and models
• Spectral analysis of large dimensional random matrices
• Consistency of community detection in networks under degree-corrected stochastic block models
• Spectral redemption in clustering sparse networks
• Robust principal component analysis?
• Fast community detection by SCORE
• Bulk universality for generalized Wigner matrices
• Stochastic blockmodels with a growing number of classes
• Title not available (Why is that?)
• Consistent Adjacency-Spectral Partitioning for the Stochastic Block Model When the Model Parameters Are Unknown
• Title not available (Why is that?)
• WHICH PART OF THE SAMPLE CONTAINS THE INFORMATION?
• User-friendly tail bounds for sums of random matrices

Cited In (93)

• Fast Network Community Detection With Profile-Pseudo Likelihood Methods
• Title not available (Why is that?)
• Optimization via low-rank approximation for community detection in networks
• Graph matching beyond perfectly-overlapping Erdős--Rényi random graphs
• Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information
• The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising
• Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
• Community detection in degree-corrected block models
• Consistency of spectral clustering in stochastic block models
• Network linear discriminant analysis
• Convexified modularity maximization for degree-corrected stochastic block models
• Overlapping community detection in networks via sparse spectral decomposition
• Bayesian community detection
• Optimal adaptivity of signed-polygon statistics for network testing
• Generalized Low-Rank Plus Sparse Tensor Estimation by Fast Riemannian Optimization
• Embedding-based silhouette community detection
• Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis
• Testing degree corrections in stochastic block models
• Community detection by \(L_{0}\)-penalized graph Laplacian
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Consistent structure estimation of exponential-family random graph models with block structure
• Profile likelihood biclustering
• Bayesian degree-corrected stochastic blockmodels for community detection
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Robust high-dimensional factor models with applications to statistical machine learning
• A distributed community detection algorithm for large scale networks under stochastic block models
• Network representation using graph root distributions
• FAST COMMUNITY IDENTIFICATION BY HIERARCHICAL GROWTH
• Network Structure Change Point Detection by Posterior Predictive Discrepancy
• Community Detection and Stochastic Block Models
• Optimality of spectral clustering in the Gaussian mixture model
• Perturbation of Linear Forms of Singular Vectors Under Gaussian Noise
• Graph Clustering Via Intra-Cluster Density Maximization
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Corrected Bayesian Information Criterion for Stochastic Block Models
• Eigen Selection in Spectral Clustering: A Theory-Guided Practice
• Network Cross-Validation for Determining the Number of Communities in Network Data
• The Interplay of Demographic Variables and Social Distancing Scores in Deep Prediction of U.S. COVID-19 Cases
• Optimal Estimation of the Number of Network Communities
• Community detection on mixture multilayer networks via regularized tensor decomposition
• Detecting Overlapping Communities in Networks Using Spectral Methods
• Spectral clustering in the dynamic stochastic block model
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fast community detection by SCORE
• Improvements on SCORE, Especially for Weak Signals
• Mixed Membership Estimation for Social Networks
• ScorePlus
• Using SVD for Topic Modeling
• A goodness-of-fit test for stochastic block models
• Title not available (Why is that?)
• Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
• Community detection for New York stock market by SCORE-CCD
• A Sparse Completely Positive Relaxation of the Modularity Maximization for Community Detection
• A spectral method for community detection in moderately sparse degree-corrected stochastic block models
• Using Maximum Entry-Wise Deviation to Test the Goodness of Fit for Stochastic Block Models
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Two-sample test of stochastic block models
• A Time-Varying Network for Cryptocurrencies
• Graph clustering with Boltzmann machines
• Consistent model selection for the degree corrected stochastic blockmodel
• A spectral based goodness-of-fit test for stochastic block models
• A survey on theoretical advances of community detection in networks
• Stock co-jump networks
• Estimating mixed-memberships using the symmetric Laplacian inverse matrix
• Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
• Community Detection in Censored Hypergraph
• Community Detection in Partial Correlation Network Models
• Discussion of “Cocitation and Coauthorship Networks of Statisticians”
• Network-Based Clustering for Varying Coefficient Panel Data Models
• Rejoinder: “Co-citation and Co-authorship Networks of Statisticians”
• Clustering heterogeneous financial networks
• Spectral Clustering on Spherical Coordinates Under the Degree-Corrected Stochastic Blockmodel
• PCABM: Pairwise Covariates-Adjusted Block Model for Community Detection
• Tractably modelling dependence in networks beyond exchangeability
• Hypothesis testing for equality of latent positions in random graphs
• Covariate-Assisted Community Detection in Multi-Layer Networks
• Two-sample test of stochastic block models via the maximum sampling entry-wise deviation
• Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM)
• Consistent Community Detection in Inter-Layer Dependent Multi-Layer Networks
• Computational lower bounds for graphon estimation via low-degree polynomials
• Leave-one-out singular subspace perturbation analysis for spectral clustering
• Applications of dual regularized Laplacian matrix for community detection
• Efficient split likelihood-based method for community detection of large-scale networks
• Community Detection in General Hypergraph Via Graph Embedding
• Community detection with nodal information: likelihood and its variational approximation
• Fallacy of data-selective inference in modelling networks
• Community detection in attributed collaboration network for statisticians
• Profile-pseudo likelihood methods for community detection of multilayer stochastic block models
• Special invited paper: the SCORE normalization, especially for heterogeneous network and text data
• Co-citation and Co-authorship Networks of Statisticians

This page was built for publication: Fast community detection by SCORE

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