PLinkSHRINK: a parallel overlapping community detection algorithm with Link-Graph for large networks

• Published in: Social network analysis and mining 2019-12, Vol.9 (1), p.66, Article 66
• Main Authors: Zhang, Yunlei, Yin, Dingyi, Wu, Bin, Long, Feiyu, Cui, Yinchang, Bian, Xun
• Format: Article
• Language: English
• Subjects: Algorithms; Applications of Graph Theory and Complex Networks; Clustering; Community; Computer networks; Computer Science; Data analysis; Data Mining and Knowledge Discovery; Density; Distributed processing; Economics; Game Theory; Humanities; Law; Methodology of the Social Sciences; Methods; Modularity; Network analysis; Optimization; Original Article; Outliers (statistics); Social and Behav. Sciences; Statistics for Social Sciences; Truth
• ISSN: 1869-5450; 1869-5469
• DOI: 10.1007/s13278-019-0609-3

Overlapping communities are pervasive in real-world networks. Therefore, overlapping community detection is an important task in network analysis. Recently, many overlapping community detection methods are proposed to achieve different goals. However, how to detect communities effectively and efficiently is still an open problem. In this paper, we use our previously proposed method LinkSHRINK to detect overlapping community detection, which is based on density structure and modularity optimization. It successfully solves the excessive overlapping problem. Moreover, it can detect both overlapping communities of multi-granularity and outliers. To deal with very large networks, we choose to sample on the large graph and then parallelize LinkSHRINK by distributed computing frameworks. Experiments are conducted on benchmark networks and some real-world networks with known ground-truth communities. The experimental results demonstrate that LinkSHRINK outperforms most of the baseline methods and its parallel versions PLinkSHRINK and MLinkSHRINK can process large networks efficiently.