Fast community detection by SCORE

DOI10.48550/ARXIV.1211.5803MaRDI QIDQ144808zbMATH OpenOpenAlexFDO

Authors Jiashun Jin

Publication date 25 November 2012

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

Full work available at URL https://arxiv.org/abs/1211.5803, https://projecteuclid.org/euclid.aos/1416322036

zbMATH Keywords

\(k\)-means methodcommunity detectiondegree corrected block model (DCBM)Hamming distancemoderate deviationmodularityPCAsocial networksparsityspectral analysis

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)

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.

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

Cites work

• A nonparametric view of network models and Newman–Girvan and other modularities
• A survey of statistical network models
• Bulk universality for generalized Wigner matrices
• Consistency of community detection in networks under degree-corrected stochastic block models
• Consistent adjacency-spectral partitioning for the stochastic block model when the model parameters are unknown
• Fast community detection by SCORE
• Forest density estimation
• scientific article; zbMATH DE number 3994822 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Matrix Analysis
• Pseudo-likelihood methods for community detection in large sparse networks
• Robust principal component analysis?
• Spectral analysis of large dimensional random matrices
• Spectral clustering and the high-dimensional stochastic blockmodel
• Spectral redemption in clustering sparse networks
• Statistical analysis of network data. Methods and models
• Stochastic blockmodels with a growing number of classes
• The elements of statistical learning. Data mining, inference, and prediction
• User-friendly tail bounds for sums of random matrices
• Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
• WHICH PART OF THE SAMPLE CONTAINS THE INFORMATION?

Cited in

(only showing first 100 items - show all)

• Graph matching beyond perfectly-overlapping Erdős--Rényi random graphs
• Fast community detection by SCORE
• Improvements on SCORE, especially for weak signals
• Mixed Membership Estimation for Social Networks
• ScorePlus
• Using SVD for Topic Modeling
• Network cross-validation for determining the number of communities in network data
• Bayesian community detection
• Community detection by \(L_{0}\)-penalized graph Laplacian
• Network linear discriminant analysis
• Community detection in degree-corrected block models
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Robust high-dimensional factor models with applications to statistical machine learning
• Network representation using graph root distributions
• Optimality of spectral clustering in the Gaussian mixture model
• Community detection on mixture multilayer networks via regularized tensor decomposition
• Optimal adaptivity of signed-polygon statistics for network testing
• Testing degree corrections in stochastic block models
• Overlapping community detection in networks via sparse spectral decomposition
• Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis
• Embedding-based silhouette community detection
• Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
• Profile likelihood biclustering
• Consistent structure estimation of exponential-family random graph models with block structure
• Consistency of spectral clustering in stochastic block models
• Robust and computationally feasible community detection in the presence of arbitrary outlier nodes
• Convexified modularity maximization for degree-corrected stochastic block models
• Perturbation of linear forms of singular vectors under Gaussian noise
• Bayesian degree-corrected stochastic blockmodels for community detection
• Graph clustering via intra-cluster density maximization
• FAST COMMUNITY IDENTIFICATION BY HIERARCHICAL GROWTH
• Community detection and stochastic block models: recent developments
• Improved spectral community detection in large heterogeneous networks
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• A sparse completely positive relaxation of the modularity maximization for community detection
• scientific article; zbMATH DE number 6962251 (Why is no real title available?)
• Universal latent space model fitting for large networks with edge covariates
• Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information
• Change point estimation in a dynamic stochastic block model
• Determining the number of communities in degree-corrected stochastic block models
• The interplay of demographic variables and social distancing scores in deep prediction of U.S. COVID-19 cases
• Detecting overlapping communities in networks using spectral methods
• Community Detection in Sparse Networks Using the Symmetrized Laplacian Inverse Matrix (SLIM)
• scientific article; zbMATH DE number 7626732 (Why is no real title available?)
• scientific article; zbMATH DE number 7626779 (Why is no real title available?)
• Network Structure Change Point Detection by Posterior Predictive Discrepancy
• Corrected Bayesian information criterion for stochastic block models
• scientific article; zbMATH DE number 7307464 (Why is no real title available?)
• A spectral method for community detection in moderately sparse degree-corrected stochastic block models
• The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising
• Optimization via low-rank approximation for community detection in networks
• A goodness-of-fit test for stochastic block models
• Using Maximum Entry-Wise Deviation to Test the Goodness of Fit for Stochastic Block Models
• Community Detection in General Hypergraph Via Graph Embedding
• Optimal Estimation of the Number of Network Communities
• A distributed community detection algorithm for large scale networks under stochastic block models
• Eigen Selection in Spectral Clustering: A Theory-Guided Practice
• Fast Network Community Detection With Profile-Pseudo Likelihood Methods
• Graph clustering with Boltzmann machines
• Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
• Generalized Low-Rank Plus Sparse Tensor Estimation by Fast Riemannian Optimization
• Stock co-jump networks
• Estimating mixed-memberships using the symmetric Laplacian inverse matrix
• Community detection for New York stock market by SCORE-CCD
• Spectral Clustering via Adaptive Layer Aggregation for Multi-Layer Networks
• Community Detection in Censored Hypergraph
• Covariate-Assisted Community Detection in Multi-Layer Networks
• Clustering heterogeneous financial networks
• Efficient split likelihood-based method for community detection of large-scale networks
• 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
• Special invited paper: the SCORE normalization, especially for heterogeneous network and text data
• Profile-pseudo likelihood methods for community detection of multilayer stochastic block models
• Two-sample test of stochastic block models
• 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
• Community Detection in Partial Correlation Network Models
• 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”
• Network-Based Clustering for Varying Coefficient Panel Data Models
• A Time-Varying Network for Cryptocurrencies
• 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
• Two-sample test of stochastic block models via the maximum sampling entry-wise deviation
• Consistent Community Detection in Inter-Layer Dependent Multi-Layer Networks
• Leave-one-out singular subspace perturbation analysis for spectral clustering
• Computational lower bounds for graphon estimation via low-degree polynomials
• Applications of dual regularized Laplacian matrix for community detection
• Spectral clustering in the dynamic stochastic block model
• A two-way heterogeneity model for dynamic networks
• Network-Based Neighborhood Regression
• Degree-Heterogeneous Latent Class Analysis for High-Dimensional Discrete Data
• A community detection algorithm based on spectral co-clustering and weight self-adjustment in attributed stochastic co-block models
• Orthogonal symmetric non-negative matrix factorization under the stochastic block model
• Community extraction of network data under stochastic block models

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)