대규모 그래프 처리를 위한 Label-Propagation 기반 병렬 그래프 파티션 기법
Parallel Graph Partitioning Scheme Based on Label-Propagation for Large-Scale Graph Data
- 주제(키워드) big graph data , graph partitioning , label propagation algorithm , parallel processing
- 발행기관 아주대학교
- 지도교수 오상윤
- 발행년도 2019
- 학위수여년월 2019. 8
- 학위명 박사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/ajou/000000029211
- 본문언어 영어
- 저작권 아주대학교 논문은 저작권에 의해 보호받습니다.
초록/요약
The increasing importance of graph data in various fields makes the efficient processing of large-scale graph data highly necessary where well-balanced graph partitioning is a vital component of parallel/distributed graph processing. The goal of graph partitioning is to obtain a well-balanced graph topology that balances the size of each partition while reducing the number of edge-cuts. Moreover, the graph partitioning algorithm should achieve high performance and scalability. In this paper, we present a novel graph-partitioning algorithm that ensures low edge-cuts and high-performance processing capability for parallel processing. Based on the label propagation algorithm, we propose the formulas to improve the degree of edge-cuts and to achieve fast convergence. By removing the necessity of processing the label propagation for all nodes, our approach processes the label propagation of candidate nodes based on a proposed score metric. Our proposed algorithm introduces a stabilization phase in which remote and highly connected nodes are relocated to avoid the algorithm becoming trapped around local optima. Comparison results show that a prototype based on the proposed algorithm outperforms other well-known parallel graph-partitioning frameworks in terms of speed and balance.
more목차
I Introduction 1
A. Motivation 1
B. Thesis Contribution 8
C. Thesis Outline 10
II Background and Related Work 11
A. Background 11
1. Categories of Graph Partitioning 11
2. Distributed Graph Processing Frameworks 16
B. Related Work 22
1. Heuristic Approaches 22
2. Multilevel Approach 31
3. State-of-the-Art Graph-Partitioning Algorithms 36
III Proposed Graph-Partitioning Algorithm 38
IV Parallel Graph-Partitioning Process 45
A. Data Structure 45
B. Parallel Graph-Partitioning Algorithm 51
1. Quick-Converging Label Propagation 51
2. Stabilization Process 62
3. Size-Constrained Partition 72
V Experiment 74
A. Experimental Environment 75
B. Comparison with Other Systems 78
1. Balance Ratio 78
2. Performance of graph partitioning 81
3. Edge-cut Result 87
C. Strong Scaling 92
VI Conclusion 94
