DyBGP: A Dynamic-Balanced Algorithm for Graph Partitioning Based on Heuristic Strategies
-
摘要: 随着计算技术的发展以及大数据时代的来临，分布式计算已成为研究的热点，其中大图迭代计算作为其研究的重点，降低划分后子图之间的通信边规模是改善计算性能的关键.传统算法很难在切割率最小化与负载均衡上同时满足.由于图划分属于NP组合优化问题，提出了一种动态平衡算法来解决图的平衡划分，确保在子图边界点划分最优的基础上引入扰动策略使其跳出局部最优扩大搜索空间，最后在真实世界图上验证算法的可行性，分别从平衡系数、切割边规模与传统算法进行了比较.在指定的扰动次数下，此算法比常见的算法hash，Chunk，Metis在割边率上分别降低了近40%，30%，5%.与Metis相比，平衡系数也更加地优化，实验结果证明了该算法的有效性.Abstract: With the development of computing technology and the advent of the era of big data, the distributed computing has became a research hotspot. Iterative computation of big graph becomes the focus of the research. Reducing the communication data quantity between subgraph after effective partitioning, it is the key to improve the computational performance, because the existing algorithms are difficult to meet the requirements on both minimizing fraction of egdes cut and load balancing at the same time. In this paper, a dynamic-balanced algorithm for graph partitioning named DyBGP is proposed, and it is used to solve the problem of balanced partition. Based on ensuring the partitioning of subgraph boundary vertices optimal, the perturbation strategy to jump out of local optimum to expand the search space is used. Finally, our algorithm is verified the feasibility in the real-world graph, respectively from the balance coefficient and the scale of edges cut compared with the traditional algorithms, such as Hash, Chunk and Metis. In the number of edges cut, it is decreased about 40%, 30%, 5% with our algorithm under specifying perturbation times. In the balance coefficient, our algorithm is more optimized than Metis. The experimental results show that the algorithm is effective.
-
-
期刊类型引用(3)
1. 商涛，程瑶，陈禄明，邓立宗，蒋太交. 呼吸病学标准医学术语在电子病历中的使用情况调研. 中国科技术语. 2021(04): 53-59 . 
百度学术
2. 郑光敏，易天源，唐东昕，贺松. 基于BERT-BiLSTM-CRF模型的中国民族药知识抽取. 武汉大学学报(理学版). 2021(05): 393-402 . 百度学术
3. 戴志宏，郝晓玲. 上下位关系抽取方法及其在金融市场的应用. 数据分析与知识发现. 2021(10): 60-70 . 百度学术
其他类型引用(4)
计量
- 文章访问数: 1705
- HTML全文浏览量: 6
- PDF下载量: 580
- 被引次数: 7
下载:
