An efficient community detection method based on rank centrality

Community detection is a very important problem in social network analysis. Classical clustering approach, K-means, has been shown to be very efficient to detect communities in networks. However, 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-rank, which selects the top-K nodes with the highest rank centrality as the initial seeds, and updates these seeds by using an iterative technique like K-means. Then we extend K-rank to partition directed, weighted networks, and to detect overlapping communities. The empirical study on synthetic and real networks show that K-rank is robust and better than the state-of-the-art algorithms including K-means, BGLL, LPA, infomap and OSLOM.