Fast and Parallel Ranking-based Clustering for Heterogeneous Graphs
Fast and Parallel Ranking-based Clustering for Heterogeneous Graphs
复制标题
基于快速并行排序的异构图聚类
DOI：
10.26421/jdi1.2-3
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
H. Kitagawa
中科院分区：
文献类型：
--
作者：
Kotaro Yamazaki;Tomoki Sato;Hiroaki Shiokawa;H. Kitagawa
人们对图形数据分析方法的需求越来越大。RankClus是一个通过在异构图上集成聚类和排序来提取聚类的框架，它通过交替更新聚类和排序的结果来增强聚类结果，以更好地理解聚类。然而，如果图很大，则RankClus的计算代价很高，因为它需要迭代所有节点的聚类和排名。本文针对这一问题，提出了一种新的异构图快速RankClus算法。为了加快RankClus的整个过程，我们提出的算法减少了每次迭代中排序过程的计算代价。我们的建议衡量了每个节点对聚类结果的影响；如果影响不大，我们就对节点进行剪枝。此外，我们还提出了一种并行算法，通过充分利用现代多核CPU对所提算法进行了扩展。结果，我们广泛的评估表明，我们的快速和并行算法大大缩短了原始算法RancClus的计算时间。
The demands for graph data analysis methods are increasing. RankClus is a framework to extract clusters by integrating clustering and ranking on heterogeneous graphs; it enhances the clustering results by alternately updates the results of clustering and ranking for the better understanding of the clusters. However, RankClus is computationally expensive if a graph is large since it needs to iterate both clustering and ranking for all nodes. In this paper, to address this problem, we propose a novel fast RankClus algorithm for heterogeneous graphs. To speed up the entire procedure of RankClus, our proposed algorithm reduces the computational cost of the ranking process in each iteration. Our proposal measures how each node affects the clustering result; if it is not significant, we prune the node. Furthermore, we also present a parallel algorithm by extending our proposed algorithm by fully exploiting a modern manycore CPU. As a result, our extensive evaluations clarified that our fast and parallel algorithms drastically cut off the computation time of the original algorithm RancClus.