摘要
针对传统的K-means算法的划分结果受初始中心节点影响较大,以及每次刷新中心节点均需要进行计算,使得算法运行时间较高等问题,提出一种基于中心度的K-means改进算法CDK算法。该算法根据节点的中心度以及节点之间的最短路径来确定初始社团的中心节点,然后根据节点之间的Jaccard相似度,将非中心节点划分到K个社团中。CDK算法避免了传统的K-means算法由于随机选取初始中心点而造成划分结果不稳定、精度较差的问题,同时CDK算法在刷新中心节点的时候无须进行计算,具有更低的时间复杂度。
Dividing the result for the traditional K-means algorithm is influenced by the initial central node, and each refresh center nodes need to be calculated, cause the higher algorithm running time and other issues. Proposes an improved algorithm based on centrality of K-means,CDK algorithm. The algorithm is based on the shortest path between the node and the node to the center of the central node determining the initial associations, then according to Jaccard similarity between nodes, will be divided into K non-central node in societies. CDK al-gorithm avoids the traditional K-means algorithm due to the random selection of initial results of the center divide and cause instability,poor accuracy problems, while CDK refresh algorithm when the central node without calculation, has a lower time complexity.