1. Fast Graph Clustering Algorithm Based on Selection of Key Nodes
- Author
-
YOU Fangzhou, BAI Liang
- Subjects
cluster analysis ,graph clustering ,spectral clustering ,cluster ensemble ,selection of key nodes ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
Spectral clustering has attracted extensive attention as a typical graph clustering algorithm among clustering algorithms since it has really strong adaptability to complex data distribution and great clustering effect. However, it is difficult to apply spectral clustering algorithm to large scale data due to the high time complexity. To address this issue, a fast graph clustering algorithm based on the selection of key nodes is proposed. This algorithm consists of three steps. Firstly, a fast node weight evaluation method is established based on thorough consideration of the clustering and separateness. Secondly, the key nodes are selected to replace the original data set to construct a bipartite graph, and the approximated eigenvectors of the data are obtained by singular value decomposition. Thirdly, multiple approximated eigenvectors are integrated to improve the robustness of the approximated spectral clustering results. The time complexity has been reduced from [O(n3)] to [O(t(n+2n2))], facilitating the application of spectral clustering algorithm to large scale data. Through experimental analysis of this algorithm against other 7 representative spectral clustering algorithms on 5 Benchmark data sets, the comparative results demonstrate that this algorithm can identify complex class structures in data more efficiently than other clustering algorithms.
- Published
- 2021
- Full Text
- View/download PDF