COMMUNITY DETECTION ALGORITHM BASED ON LOCAL EXPANSION K-MEANS

L. Li ； K. Fan ； Z. Zhang ； Z. Xia

《Neural Network World》 26卷6期 (2016/12) Pp. 589-605

https://doi.org/10.14311/NNW.2016.26.034

摘要

Community structure implies some features in various real-world networks, and these features can help us to analysis structural and functional properties in the complex system. It has been proved that the classic k-means algorithm can efficiently cluster nodes into communities. However, initial seeds decide the efficiency of the k-means, especially when detecting communities with different sizes. To solve this problem, we improve the classic community detection algorithm with Principal Component Analysis(PCA) mapping and local expansion k-means. Since PCA can preserve the distance information of every node pairs, the improved algorithm use PCA to map nodes in the complex network into lower dimension European space, and then detect initial seeds for k-means using the improved local expansion strategy. Based on the chosen initial seeds, the k-means algorithm can cluster nodes into communities. We apply the proposed algorithm in real-world and artificial networks, the results imply that the improved algorithm is efficient to detect communities and is robust to the initial seed of K-means.

關鍵字

community structure ； PCA ； Local Expansion Strategy