A robust two-stage algorithm for local community detection

摘要

Local community detection addresses the efficiency problem faced by global community detection. Most existing local community detection algorithms take a seed as an initial community. They extend the community by running a greedy optimization process for a quality function. However, the quality of the detected community depends on the location of the seed. This leads to seed-dependent problem. Besides that, many local community detection algorithms cannot ensure the seed exists in the detected community. This leads to seed-invalid problem. This article proposes a robust two-stage local community detection algorithm (RTLCD) based on core detecting and community extension. To solve the seed-dependent problem, the core detecting stage replaces the seed with the core member of the target community. To solve the seed-invalid problem, the community extension stage takes the detected community core member as an initial community and extends the community based on relation strength. Experimental results on artificial and real-world networks show that RTLCD is more robust to the seed-dependent problem and the seed-invalid problem than earlier state-of-the-art algorithms. In addition, RTLCD has excellent performance in identifying more ground-truth community members.