Finding Community Structure in Networks Using a Shortest-Path-Based $k$-Means Algorithm
Received:December 08, 2011  Revised:December 20, 2011
Key Words: community structure   modularity   shortest path   $K$-means   simulated annealing.  
Fund Project:Supported by the National Natural Science Foundation of China (Grant No.10771085).
Author NameAffiliation
Jinglu GAO School of Mathematics, Jilin University, Jilin 130012, P. R. China 
Hits: 3296
Download times: 4063
      We consider the problem of detecting the community structure in a complex network, groups of nodes with a higher-than-average density of edges connecting them. In this paper we use the simulated annealing strategy to maximize the modularity, which has been indicated as a robust benefit function, associating with a shortest-path-based $k$-means iterative procedure for network partition. The proposed algorithm can not only find the communities, but also identify the nodes which occupy central positions under the metric of the shortest path within the communities to which they belong. The optimal number of communities can be automatically determined without any prior knowledge about the network structure. The applications to both artificial and real-world networks demonstrate the effectiveness of our algorithm.
View Full Text  View/Add Comment  Download reader