A novel community detection algorithm based on simplification of complex networks

摘要

Efficiently discovering the hidden community structure in a network is an important research concept for graph clustering. Although many detection algorithms have been proposed, few of them provide a visual understanding of the community structure in a network. In this paper, we define two measurements about the leading and following degrees of a node. Based on the measurements, we provide a new representation method for a network, which transforms it into a simplified network, i.e., weighted tree (or forest). Compared to the original network, the simplified network can easily observe the community structure. Furthermore, we present a detection algorithm which finds out the communities by min-cutting the simplified network. Finally, we test the performance of the proposed algorithm on several network data sets. The experimental results illustrate that the proposed algorithm can visually and effectively uncover the community structure.