Community Detection Based on the $L_{\infty }$ convergence of eigenvectors in DCBM

Abstract

Spectral clustering is one of the most popular algorithms for community detection in network analysis. Based on this rationale, in this paper we give the convergence rate of eigenvectors for the adjacency matrix in the $l_{\infty }$ norm, under the stochastic block model (BM) and degree corrected stochastic block model (DCBM), adding some mild and rational conditions. We also extend this result to a more general model, presented based on the DCBM such that the value of random variables in the adjacency matrix is not 0 or 1, but an arbitrary real number. During the process of proving the above conclusion, we obtain the relationship of the eigenvalues in the adjacency matrix and the corresponding `population' matrix, which vary in dimension from the community-wise edge probability matrix. Using that result, we can give an estimate of the number of the communities in a known set of network data. Meanwhile we proved the consistency of the estimator. Furthermore, according to the derivation of proof for the convergence of eigenvectors, we propose a new approach to community detection -- Spectral Clustering based on Difference of Ratios of Eigenvectors (SCDRE). Our simulation experiments demonstrate the superiority of our method in community detection.

arXiv comment28 pages, 2 figures

References in corpus (10)

• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• The structure of scientific collaboration networks
• Stochastic blockmodels and community structure in networks
• Social Structure of Facebook Networks
• Mixture models and exploratory analysis in networks
• Fast community detection by SCORE
• Community extraction for social networks

Cited by in corpus (2)

• Improvements on SCORE, Especially for Weak Signals
• Estimating Graph Dimension with Cross-validated Eigenvalues