大规模图数据划分算法综述

doi:10.3969/j.issn.1000-0801.2014.07.016

摘要/Abstract

摘要：

摘要：对大规模图数据划分算法进行了总结，介绍了并行环境下图计算模型，详述了大规模静态图划分算法和动态图划分算法，归纳了这些算法的优缺点以及适应性。最后，指出了关于大图划分尚未探索的有意义的研究课题。

关键词: 大数据, 大图, 分布式图划分, 负载均衡, BSP, MapReduce, 动态图

Abstract:

The large-scale graph partitioning algorithms were summarized and graph computing models in the distributed environment were introduced. Firstly the large-scale static graph partitioning algorithms and the dynamic graph partitioning algorithms were discussed. Then the advantages and disadvantages of these algorithms and its adaptability conscientiously were sumed up. Finally, some meaningful research subjects about the distributed graph partition, which have not been explored were pointed out.

Key words: big data, large-scale graph, distributed graph partitioning, load balancing, bulk synchronous parallel model, MapReduce, dynamic graphs

许金凤,董一鸿,王诗懿,何贤芒,陈华辉. 大规模图数据划分算法综述[J]. 电信科学, 2014, 30(7): 100-106.

Jinfeng Xu,Yihong Dong,Shiyi Wang,Xianmang He,Huahui Chen. Summary of Large-Scale Grapb Partitioning Algoritbms[J]. Telecommunications Science, 2014, 30(7): 100-106.

图/表 5

图1

图2

图3

图4

表1

参考文献 24

1	Dutt S . New faster kernighan-lin-type graph-partitioning algorithms. IEEE/ACM International Conference on IEEE, Santa Clara, CA, USA, 1993: 370～377
2	Fiduccia C M , Mattheyses R M . A linear-time heuristic for improving network partitions. 19th Conference on IEEE, Las Vegas, NV, USA, 1982: 175～181
3	Pothen A , Simon H D , Liou K P . Partitioning sparse matrices with eigenvectors of graphs. IAM Journal on Matrix Analysis and Applications, 1990, 11 (3): 430～452
4	Karypis G , Kumar V . A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing, 1998,20 (1): 359～392
5	周爽，鲍玉斌，王志刚等． BHP：面向BSP 模型的负载均衡Hash图数据划分．计算机科学与探索， 2014,8(1): 40～50
6	Kalnis P , Khayyat Z , Awara K ,et al. Mizan:optimizing graph mining in large parallel systems.
7	Ugander J , Backstrom L . Balanced label propagation for partitioning massive graphs. Proceedings of the sixth ACM International Conference on Web Search and Data Mining. ACM, Rome, Italy, 2013: 507～516.
8	Khayyat Z , Awara K , Alonazi A , et al. Mizan: a system for dynamic load balancing in large-scale graph processing. Proceedings of the 8th ACM European Conference on Computer Systems, Prague, Czech Republic, 2013
9	Vaquero L , Cuadrado F , Logothetis D ,et al. xdgp: a dynamic graph processing system with adaptive partitioning.
10	Tsourakakis C E , Gkantsidis C , Radunovic B , et al. Fennel:Streaming Graph Partitioning for Massive Scale Graphs. Microsoft Technical Report MSR-TR-2012-113, 2012
11	Karypis G , Kumar V . Metis-unstructured graph partitioning and sparse matrix ordering system,version 2.0.
12	Stanton I, , Kliot G . Streaming graph partitioning for large distributed graphs. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing, China , 2012
13	Dean J , Ghemawat S . MapReduce: simplified data processing on large clusters. Communications of the ACM, 2008, 51(1): 107～113
14	White T . Hadoop:The Definitive Guide. OˊReilly Media,Inc, 2012
15	Condie T , Conway N , Alvaro P ,et al. MapReduce Online. NSDI 2010, San Jose, USA, 2010
16	Bu Y , Howe B , Balazinska M . et al. HaLoop: efficient iterative data processing on large clusters. Proceedings of the VLDB Endowment, 20103(1-2): 285～296
17	Ekanayake J , Li H , Zhang B , et al. Twister: a runtime for iterative MapReduce. Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing, New York, NY, USA , 2010
18	Zhang Y , Gao Q , Gao L , et al. Priter: a distributed framework for prioritized iterative computations. Proceedings of the 2nd ACM Symposium on Cloud Computing, San Jose, USA , 2011
19	Valiant L G . A bridging model for parallel computation. Communications of the ACM, 199033 (8): 103～111.
20	Malewicz G , Austern M H , Bik A J C ,et al. Pregel: a system for large-scale graph processing. Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, Snowbird, UT, USA , 2010: 135～146
21	Avery C . Giraph: large-scale graph processing infrastructure on Hadoop. Proceedings of the Hadoop Summit, Santa Clara, USA, 2011
22	Boyd S P , Vandenberghe L . Vandenberghe L. Cambridge: Cambridge University Press , 2004
23	Salihoglu S , Widom J . GPS: A Graph Processing System. Stanford University
24	Bao N T , Suzumura T . Towards highly scalable pregel-based graph processing platform with x10. Proceedings of the 22nd International Conference on World Wide Web Companion, International World Wide Web Conferences Steering Committee, Seoul, Korea, 2013: 501～508

算法	优点	缺点	适用范围
散列	简单易实现，负载均衡	没有考虑图的结构性，边割多	静态图划分，初始划分
BHP	负载均衡，边割相对散列少	没有考虑图的结构性	静态图划分，初始划分
静态Mizan	将图分类进行分别处理	幂律图划分开销大非幂律图有时延	静态图划分
BLP	负载均衡，边割相对少	时间复杂度大	静态图划分
动态Mizan	负载均衡	没有考虑图的结构性，边割没有限制	动态图
xDGP	考虑图的结构性，边割少	负载均衡没有很好地控制	动态图

[1]	韩璐, 陈威宇, 张斐, 何建锋, 苏怀振. 差异化需求下的非关系型分布式报送信息大数据分类方法[J]. 电信科学, 2023, 39(6): 114-121.
[2]	韩雪. 基于电力大数据的电力骨干通信网络毁伤韧性评估方法[J]. 电信科学, 2023, 39(5): 136-143.
[3]	孙玉娣. 基于电信大数据的5G网络海量用户复访行为预测模型[J]. 电信科学, 2023, 39(2): 157-162.
[4]	丁雨, 李晨凯, 韩会梅, 卢为党, 任元红, 高原, 曹江. 基于5G无人机通信的多智能体异构网络选择方法[J]. 电信科学, 2022, 38(8): 28-36.
[5]	李爱华, 吴晓波, 陈超, 魏彬, 史嫄嫄. 5G网络大数据智能分析技术[J]. 电信科学, 2022, 38(8): 129-139.
[6]	黄更生, 黄宇红, 郭漫雪, 郑健平, 葛欣. DT时代面向数据服务的新型基础设施架构[J]. 电信科学, 2022, 38(7): 138-145.
[7]	李攀攀, 谢正霞, 乐光学, 刘鑫. 基于深度学习的无线通信接收方法研究进展与趋势[J]. 电信科学, 2022, 38(2): 1-17.
[8]	赵海波, 相志军, 肖林松. 基于异构数据的电力短期负荷大数据预测方案[J]. 电信科学, 2022, 38(12): 103-111.
[9]	王兆辉, 沈剑良, 张霞, 陈艇. FALB：一种FC协议链路聚合算法[J]. 电信科学, 2021, 37(9): 105-111.
[10]	刘志勇, 何忠江, 阮宜龙, 单俊峰, 张超. 大数据安全特征与运营实践[J]. 电信科学, 2021, 37(5): 160-169.
[11]	刘晓军,武娟,徐晓青. 大数据架构剖析及数据安全融合技术[J]. 电信科学, 2020, 36(7): 146-155.
[12]	刘玉娇,宋坤煌,王向. 基于电力大数据的经济景气指数分析[J]. 电信科学, 2020, 36(6): 166-171.
[13]	罗斯宁,王化龙,李弘宇,彭蔚. 基于改进蚁群算法的云计算用户任务调度算法[J]. 电信科学, 2020, 36(2): 95-100.
[14]	程卫华,何肖嵘. 基于大数据的网页浏览质差分析方法研究[J]. 电信科学, 2020, 36(11): 174-181.
[15]	高建,陈文彬,庞建民,于华东,宋国瑞. 基于组合密钥的智能电网多源数据安全保护[J]. 电信科学, 2020, 36(1): 134-138.