A novel high-quality community detection algorithm based on modified K-means clustering

作者：Li Jingyong; Huang Lan; Bai Tian; Wang Zhe^*

来源：International Journal of Advancements in Computing Technology, 2012, 4(11): 248-256.

DOI：10.4156/ijact.vol4.issue 11.26

• Community detection
• Community detection algorithms
• High quality
• Initialization methods
• K-means clustering
• K-means clustering method
• Prior information
• Similarity measure
• Two-stage methods

Some existing community detection algorithms have the defect that they need extra parameters (e.g. the number of communities) as input, while other algorithms needn't to know prior information but have parameters notoriously difficult to adjust. In this paper, we present a new community detection algorithm based on modified k-means clustering method to overcome these problems. In our algorithm, we first present a new initialization method that can find initial cores no matter the number of communities is known or not and each core is regarded as a initial community. We also propose a novel two-stage method to assign nodes to corresponding communities, and then recalculate the core of each community. By repeating steps above until convergence, we get a division of a network. A series of experimental results demonstrate the performance of our proposed algorithm.

• 出版日期2012