LinkSHRINK: Overlapping Community Detection with Link-Graph

Overlapping communities are pervasive in real-world networks. Therefore overlapping community detection is an important task for mining the structure and function of complex networks. Recently, many overlapping detection methods are proposed. Though achieving different goals, how to improve the performances of the community detection algorithms is still an open problem. In this paper, we propose a novel overlapping community detection algorithm, LinkSHRINK, based on the link graph. Our proposed method, which successfully solves the excessive overlapping problem, is based on density-structure information and modularity optimization. Moreover, it can not only detect overlapping communities, but also identify outliers. In addition, algorithm LinkSHRINK can reveal the overlapping communities of multi-granularity. Experiments for evaluating the performances of our algorithm are conducted in benchmark networks and some real-world networks with known underlying communities. The experimental results demonstrate that our algorithm LinkSHRINK performs better than most of the traditional ones