期刊名称：Journal of King Saud University @?C Computer and Information Sciences
印刷版ISSN：1319-1578
出版年度：2022
卷号：34
期号：6
页码：3673-3684
语种：English
出版社：Elsevier
摘要：Clustering on graphs (networks) is becoming intractable due to increasing sizes. Nyström spectral graph clustering (NSC) is a popular method to circumvent the problem. However, NSC currently faces two issues: (1) how to efficiently obtain representative samples for large networks; (2) the NSC is irrational for the mapping of nodes. To address the issues, in this paper, we propose an improved Nyström spectral graph clustering based on k-core decomposition sampling for large networks. In the proposed method, we first employ k-core decomposition as a sampling method, then use the samples to conduct the NSC to acquire the clusters of the sample nodes and the nodes connected with the samples, and finally utilize the proposed label propagation algorithm to group the remaining nodes into previously found clusters. To evaluate the performance, we use spectral clustering and NSC as baselines and compare our algorithm with the baselines on 9 small networks. Moreover, the proposed method is applied to 5 large networks. The proposed method can achieve a Modularity of 0.355 and cost 1234.95 s for a large network with approximately 120 million edges, which demonstrates that the proposed method has higher accuracy than NSC and higher efficiency than spectral clustering.
