Detecting Overlapping Communities from Local Spectral Subspaces

摘要: Based on the definition of local spectral subspace, we propose a novel approach called LOSP for overlapping community detection. Instead using invariant subspace spanned by dominant eigenvectors entire network, run power method few steps to approximate leading that depict embedding neighborhood structure around seeds interest. We then seek sparse indicator vector in these vectors such are its support. We evaluate five large real world networks across various domains with labeled ground-truth communities and compare results state-of-the-art detection approaches. identifies members target high accuracy from very seed members, outperforms Heat Kernel or PageRank diffusions as well global baselines. Two candidate definitions analyzed, different scoring functions determining boundary, including two new metrics, thoroughly evaluated. The structural properties sets impact set size discussed. observe low degree behave better, is robust even when started single random seed. Using subroutine starting each ego connected component, try harder yet significant task identifying all vertex in. Experiments show proposed achieves F1 measures detected multiple containing vertex.