4.7 Article

Practical and high-quality partitioning algorithm for large-scale and time-evolving graphs

期刊

KNOWLEDGE-BASED SYSTEMS
卷 227, 期 -, 页码 -

出版社

ELSEVIER
DOI: 10.1016/j.knosys.2021.107211

关键词

Time-evolving graph; Graph partitioning; Distributed graph processing; Cross partition edge; Load balance

资金

  1. National Natural Science Foundation of China [61702408, 51634007]
  2. Natural Science Foundation of Shaanxi Province, China [2019JM-020, 2019GY-056, 2020JM-526]
  3. Major Science and Technology Innovation Projects in Shandong Province, China [2019JZZY020326]
  4. Innovation Group for Interdisciplinary Computing Technologies, Xi'an University of Science and Technology

向作者/读者索取更多资源

This paper investigates the partitioning problem of dynamic and large-scale graphs, proposing a practical and high-quality graph partitioning algorithm that reduces the number of cross partition edges while maintaining a similar level of load balance by assigning vertices in the delta graph to properly chosen partitions.
With the appearance of widespread large-scale graph data, distributed graph processing grows in popularity. In order to store and analyze a large-scale graph in a distributed manner, the graph should be properly partitioned in advance. Although the partitioning of static graphs has been sufficiently investigated, the emerging graphs nowadays are typically dynamic or time-evolving. State-of-the-art partitioning algorithms for such large-scale and time-evolving graphs either are impractical because of the complexity caused by the global optimization or sacrifice partitioning quality due to a huge number of cross partition edges. This paper investigates the problem and proposes a new practical and high-quality graph partitioning algorithm. First, graph updates accumulated in a time interval are expressed as a delta graph. Second, vertices in the delta graph are classified into several subsets based on a non-overlapping community detection method. Third, vertices in the same subset are assigned to a properly chosen partition as a whole. The chosen partition is lightly loaded as well as closely related with vertices in the subset. Experimental results show that compared with the widely used hash-based and heuristic-based partitioning algorithms, our proposed algorithm gains significant decrease in terms of the number of cross partition edges while maintaining a similar level of load balance. (C) 2021 Elsevier B.V. All rights reserved.

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.7
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据