.png){kind=icon}
返回
Practical and high-quality partitioning algorithm for large-scale and time-evolving graphs
.png){kind=icon}
PRE
AI
DOI：10.1016/j.knosys.2021.107211.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
Time-evolving graph
Graph partitioning
Distributed graph processing
Cross partition edge
Load balance
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
K
IF:
7.6
论文数:
1.3W
被引数:
4.5W
机构
引用论文
Weight and age at puberty in female and male mice of strains selected for large and small body size
OAAI
OAAI分享收藏The Interpretation of Perioperative Lactate Abnormalities in Patients Undergoing Cardiac SurgeryOAAI
OAAI分享收藏Parallel Heuristics for Balanced Graph Partitioning Based on Richness of Implicit Knowledge.png)
IEEE ACCESSOAAI
IEEE ACCESSIF3.6
OAAI分享收藏
分享收藏分享收藏
查看更多内容