一种基于K-means改进的社区发现算法

An Improved Community Detection Algorithm Based on K-means Algorithm

传统的社区发现算法往往时间复杂度较高,K-means算法作为聚类算法且时间复杂度较低可为社区发现提供新思路,但K-means算法的原始应用场景为数值环境与社交网络不符,且自身存在初始中心节点选取敏感等原有问题,针对上述问题本文在下面三个方面进行了优化:第一,结合最短路径及共同邻居信息重新定义距离度量;第二,结合了节点的度和节点距离因素进行初始中心节点选取;第三,在K-means算法结果的基础上进行基于贪心策略以模块度为目标的层次聚类优化。通过实验表明:改进的K-means算法能够很好地应用于社区发现,得到的社区发现结果有较高质量。

The time complexity of traditional community detection algorithm is high. The K-means algorithm is a clustering algorithm and has a low time complexity, so it can provide new ideas for community detection. But the K-means algorithm is applied to the numerical environment, which is not in conformity with the social network. And there are some problems in the K-means algorithm, such as the selection of sensitivityto the initial center node. In view of the above problems, this paper optimizes the following three aspects： First, redefine the distance with the shortest path and the common neighbor information. Second, the initial center node is selected by the node degree and the node distance. Third, doing hierarchical clustering for the results of the K-means algorithm. The experiment shows that the improved K-means algorithm can be used in community detection well, and the results of community detection are of high quality.