Krylov Subspace Approximation for Local Community Detection in Large Networks

Abstract

Community detection is an important information mining task to uncover modular structures in large networks. For increasingly common large network data sets, global community detection is prohibitively expensive, and attention has shifted to methods that mine local communities, i.e. identifying all latent members of a particular community from a few labeled seed members. To address such semi-supervised mining task, we systematically develop a local spectral subspace-based community detection method, called LOSP. We define a family of local spectral subspaces based on Krylov subspaces, and seek a sparse indicator for the target community via an ${\ell }_1$ norm minimization over the Krylov subspace. Variants of LOSP depend on type of random walks with different diffusion speeds, type of random walks, dimension of the local spectral subspace and step of diffusions. The effectiveness of the proposed LOSP approach is theoretically analyzed based on Rayleigh quotients, and it is experimentally verified on a wide variety of real-world networks across social, production and biological domains, as well as on an extensive set of synthetic LFR benchmark datasets.

arXiv commentSubmitted to ACM Transactions on Knowledge Discovery from Data (under revision)

References in corpus (10)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Fast algorithm for detecting community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Benchmark graphs for testing community detection algorithms
• Link communities reveal multiscale complexity in networks
• Finding statistically significant communities in networks
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• Spectral methods for network community detection and graph partitioning
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks