Abstract: There is increasing interest in the study of community detection for sparse networks. Here, we propose a new method for detecting communities in sparse networks that uses the symmetrized Laplacian inverse matrix (SLIM) to measure the closeness between nodes. The idea comes from the first hitting time in random walks, and has a nice interpretation in diffusion maps. Community membership is acquired by applying the spectral method to the SLIM. The SLIM outperforms state-of-art methods in many real data sets and simulations. It is also robust to the choice of tuning parameter, in contrast to spectral clustering with regularization. Theoretical analyses show that in sparse scenarios generated by stochastic block model, the SLIM ensures the same order of misclassification rate in E (degree) as that of regularized spectral clustering.

Key words and phrases: Community, Random walk, Sparse network, Spectral method, Stochastic block model.