.png){kind=icon}
返回
A multi-objective partitioning algorithm for large-scale graph based on NSGA-II
.png){kind=icon}
PRE
AI
DOI：10.1016/j.eswa.2024.125756.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Graph partitioning plays a crucial role in distributed graph computation. The existing algorithms often formulate the partition problem as a single objective optimization problem focusing on load balancing and minimizing communication overhead, which is difficult to achieve optimization for multiple objectives and neglects communication balance. This paper formulates the problem of graph partitioning as a multi-objective constrained optimization problem, and proposes an enhanced NSGA-II to solve it. The objectives include achieving load balance, minimizing the communication overhead, and keeping communication balance. After partitioning the graph according to the vertices' degrees in first, the NSGA-II combined neighbor search is applied to guide the vertices migration to obtain the best partition result. Compared with Hash, GAP, HLP, CP_WSG, and SPNL using dataset from SNAP, the experiments performed on a cluster of 4 computing nodes demonstrate that the load balance ratio and cut-edge ratio of the proposed algorithm is almost the same with those of the best existing algorithm, and it can achieve the better cut-edge balance ratio and communication balance ratio than the other algorithms.
Keyword:
Graph partitioning
Multi-objective optimization
NSGA-II
Load balance
Communication balance
期刊
IF:
7.5
论文数:
3.0W
被引数:
10.2W
机构
暂无机构信息
引用论文
Effects of Nozzle Diameter and Number of Carbon Atoms in Fuel on Flame Quenching in Counter Burner
PREAI
分享收藏分享收藏DRONE: An Efficient Distributed Subgraph-Centric Framework for Processing Large-Scale Power-law GraphsDRONE: 一种处理大规模幂律图的高效分布式子图框架
PREAI
分享收藏Dynamic Graph Partitioning Scheme for Supporting Load Balancing in Distributed Graph Environments分布式图环境中支持负载均衡的动态图划分方案.png)
IEEE ACCESS
OAAI
IEEE ACCESSIF3.6
OAAI分享收藏
查看更多内容