Locally-biased spectral approximation for community detection

• Published in: Knowledge-based systems 2019-01, Vol.164, p.459-472
• Main Authors: Shi, Pan, He, Kun, Bindel, David, Hopcroft, John E.
• Format: Article
• Language: English
• Subjects: Algorithms; Approximation; Communities; Community; Community detection; Datasets; Diffusion rate; Domains; Eigenvalues; Eigenvectors; Graph theory; Iterative methods; Kernels; Lanczos method; Local spectral approximation; Mathematical analysis; Power iteration; Random walk; Search engines; Seeds; State of the art
• ISSN: 0950-7051; 1872-7409
• DOI: 10.1016/j.knosys.2018.11.012

We propose a Locally-Biased Spectral Approximation (LBSA) approach for identifying all latent members of a local community from very few seed members. To reduce the computation complexity, we first apply a fast random walk, personalized PageRank and heat kernel diffusion to sample a comparatively small subgraph covering almost all potential community members around the seeds. Then starting from a normalized indicator vector of the seeds and by a few steps of either Lanczos iteration or power iteration on the sampled subgraph, a local eigenvector is gained for approximating the eigenvector of the transition matrix with the largest eigenvalue. Elements of this local eigenvector is a relaxed indicator for the affiliation probability of the corresponding nodes to the target community. We conduct extensive experiments on real-world datasets in various domains as well as synthetic datasets. Results show that the proposed method outperforms state-of-the-art local community detection algorithms. To the best of our knowledge, this is the first work to adapt the Lanczos method for local community detection, which is natural and potentially effective. Also, we did the first attempt of using heat kernel as a sampling method instead of detecting communities directly, which is proved empirically to be very efficient and effective.