An efficient community detection method based on rank centrality

Community detection is a very important problem in social network analysis. Classical clustering approach, K$K$-means, has been shown to be very efficient to detect communities in networks. However, K$K$-means is quite sensitive to the initial centroids or seeds, especially when it is used to detect communities. To solve this problem, in this study, we propose an efficient algorithm K$K$-rank, which selects the top-K$K$ nodes with the highest rank centrality as the initial seeds, and updates these seeds by using an iterative technique like K$K$-means. Then we extend K$K$-rank to partition directed, weighted networks, and to detect overlapping communities. The empirical study on synthetic and real networks show that K$K$-rank is robust and better than the state-of-the-art algorithms including K$K$-means, BGLL, LPA, infomap and OSLOM.