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.