Fast community detection by SCORE

DOI10.48550/ARXIV.1211.5803MaRDI QIDQ144808zbMATH OpenOpenAlexFDO

Authors Jiashun Jin, 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

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)

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

• 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?)
• 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
• 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

(94)

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

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)