Improvements on SCORE, especially for weak signals

DOI10.48550/ARXIV.1811.05927zbMATH Open1490.62158arXiv1811.05927OpenAlexW3134559498MaRDI QIDQ144809FDOQ144809

Shengming Luo, Zheng Tracy Ke, Shengming Luo, Jiashun Jin, Zheng Tracy Ke, Jiashun Jin

Publication date: 14 November 2018

Published in: Sankhyā. Series A (Search for Journal in Brave)

Abstract: A network may have weak signals and severe degree heterogeneity, and may be very sparse in one occurrence but very dense in another. SCORE (Jin, 2015) is a recent approach to network community detection. It accommodates severe degree heterogeneity and is adaptive to different levels of sparsity, but its performance for networks with weak signals is unclear. In this paper, we show that in a broad class of network settings where we allow for weak signals, severe degree heterogeneity, and a wide range of network sparsity, SCORE achieves prefect clustering and has the so-called "exponential rate" in Hamming clustering errors. The proof uses the most recent advancement on entry-wise bounds for the leading eigenvectors of the network adjacency matrix. The theoretical analysis assures us that SCORE continues to work well in the weak signal settings, but it does not rule out the possibility that SCORE may be further improved to have better performance in real applications, especially for networks with weak signals. As a second contribution of the paper, we propose SCORE+ as an improved version of SCORE. We investigate SCORE+ with 8 network data sets and found that it outperforms several representative approaches. In particular, for the 6 data sets with relatively strong signals, SCORE+ has similar performance as that of SCORE, but for the 2 data sets (Simmons, Caltech) with possibly weak signals, SCORE+ has much lower error rates. SCORE+ proposes several changes to SCORE. We carefully explain the rationale underlying each of these changes, using a mixture of theoretical and numerical study.

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

Recommendations

• Fast community detection by SCORE
• Pseudo-likelihood methods for community detection in large sparse networks
• A spectral method for community detection in moderately sparse degree-corrected stochastic block models
• Covariate regularized community detection in sparse graphs
• Improved spectral community detection in large heterogeneous networks

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)

Cites Work

• Consistency of community detection in networks under degree-corrected stochastic block models
• Convexified modularity maximization for degree-corrected stochastic block models
• Mixed membership stochastic blockmodels
• Community structure in social and biological networks
• Fast community detection by SCORE
• Community detection in degree-corrected block models
• Title not available (Why is that?)
• Title not available (Why is that?)
• Detecting Overlapping Communities in Networks Using Spectral Methods
• Coauthorship and citation networks for statisticians
• Strong Consistency of Spectral Clustering for Stochastic Block Models

Cited In (4)

• Applications of dual regularized Laplacian matrix for community detection
• ScorePlus
• Community detection for New York stock market by SCORE-CCD
• Special invited paper: the SCORE normalization, especially for heterogeneous network and text data

This page was built for publication: Improvements on SCORE, especially for weak signals

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