Computer Science ›› 2016, Vol. 43 ›› Issue (4): 231-234.doi: 10.11896/j.issn.1002-137X.2016.04.047

Previous Articles     Next Articles

Relaxed Optimal Balanced Streaming Graph Partitioning Algorithm

YIN Xiao-bo and LUO En   

  • Online:2018-12-01 Published:2018-12-01

Abstract: During the distributed processing of large scale graph data,it usually needs to partition the whole graph into different nodes.If the partition isn’t balanced,some of the nodes may be the bottleneck of the distributed system.In order to achieve a balanced partition and handle the quick updates of graph efficiently,this paper proposed a relaxed optimal balanced streaming graph partitioning algorithm.Firstly,we defined an objective function including costs of both inter-partitions and intra-partition as the general graph partition framework.Secondly,we analyzed the graph partition problem according to a maximal and a minimal optimization functions based within the proposed framework,and gave their relationships.Finally,we proposed a greedy optimal graph k-partitions algorithm upon the streaming graph.The experiments show that,the proposed graph partitioning algorithm have better balance and lower communication cost than related works,and upper applications upon this algorithm have better performance.

Key words: Graph,Balanced graph partitioning,Distributed computing,Heuristic algorithm

[1] Kwak H,Lee C,Park H,et al.What is Twitter,a social network or a news media?[C]∥Proceedings of the 19th International Conference on World Wide Web.ACM,2010:591-600
[2] Xu Da-chuan,Han Ji-ye,Du Dong-lei.Improved Approximation Algorithm for Graph Partition Problem[J].Acta Mathematica Applicatae Sinica,2006,8(4):587-597(in Chinese) 徐大川,韩继业,杜东雷.关于图划分问题的改进的近似算法[J].应用数学学报,2006,28(4):587-597
[3] Malewicz G,Austern M H,Bik A J C,et al.Pregel:a system for large-scale graph processing[C]∥Proceedings of the 2010 ACM SIGMOD International Conference on Management of data.ACM,2010:135-146
[4] Kang U,Tsourakakis C E,Faloutsos C.Pegasus:A peta-scalegraph mining system implementation and observations[C]∥Ninth IEEE International Conference on Data Mining,2009(ICDM609).IEEE,2009:229-238
[5] Low Y,Bickson D,Gonzalez J,et al.Distributed GraphLab:a framework for machine learning and data mining in the cloud[J].Proceedings of the VLDB Endowment,2012,5(8):716-727
[6] Szell M,Lambiotte R,Thurner S.Multirelational organization of large-scale social networks in an online world[J].Proceedings of the National Academy of Sciences,2010,107(31):13636-13641
[7] Garey M R,Johnson D S,Stockmeyer L.Some simplified NP-complete problems[C]∥Proceedings of the sixth Annual ACM Symposium on Theory of Computing.ACM,1974:47-63
[8] Zhou Shuang,Bao Yu-bin,Wang Zhi-gang,et al.BHP:BSP Mo-del Oriented Hash Graph Data Partition with Load Balancing[J].Journal of Frontiers of Computer Science & Technology,2014,8(1):40-50(in Chinese) 周爽,鲍玉斌,王志刚,等.BHP:面向 BSP 模型的负载均衡 Hash 图数据划分[J].计算机科学与探索,2014,8(1):40-50
[9] Ke Q,Prabhakaran V,Xie Y,et al.Optimizing data partitioning for data-parallel computing[C]∥HotOS XIII.May 2011
[10] Berger-Wolf T Y,Saia J.A framework for analysis of dynamic social networks[C]∥Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mi-ning.ACM,2006:523-528
[11] Naaman M,Boase J,Lai C H.Is it really about me?message content in social awareness streams[C]∥Proceedings of the 2010 ACM Conference on Computer Supported Cooperative Work.ACM,2010:189-192
[12] Stanton I,Kliot G.Streaming graph partitioning for large distributed graphs[C]∥Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mi-ning.ACM,2012:1222-1230
[13] Krauthgamer R,Naor J S,Schwartz R.Partitioning graphs into balanced components[C]∥Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms.Society for Industrial and Applied Mathematics,2009:942-949
[14] Lin Jiao,Chen Wen-guang,Li Qiang,et al.A New Data Clustering Algorithm for Parallel Whole-Genome Shotgun Sequence Assembly[J].Journal of Computer Research and Development,2006,3(8):1323-1329(in Chinese) 林皎,陈文光,栗强,等.基于图划分的全基因组并行拼接算法[J].计算机研究与发展,2006,43(8):1323-1329
[15] Karypis G,Kumar V.A fast and high quality multilevel scheme for partitioning irregular graphs[J].SIAM Journal on scientific Computing,1998,20(1):359-392
[16] Prabhakaran V,Wu M,Weng X,et al.Managing Large Graphs on Multi-Cores with Graph Awareness[C]∥USENIX Annual Technical Conference.2012:41-52
[17] Newman M E J.The structure and function of complex net-works[J].SIAM Review,2003,45(2):167-256
[18] Tsourakakis C,Bonchi F,Gionis A,et al.Denser than the densest subgraph:Extracting optimal quasi-cliques with quality guarantees[C]∥Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2013:104-112
[19] Stanton I,Kliot G.Streaming graph partitioning for large distributed graphs[C]∥Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mi-ning.ACM,2012:1222-1230
[20] Zafarani R,Cole W D,Liu H.Sentiment propagation in social networks:a case study in livejournal[M]∥Advances in Social Computing.Springer Berlin Heidelberg,2010:413-420
[21] Leng Yong-lin,Shen Hua,Lu Fu-yu.Distributed Storage of RDF Directed Graph Based on P-Rank Algorithm[J].Journal of Chongqing University of Technology (Natural Science),2015,9(1):91-95(in Chinese) 冷泳林,申华,鲁富宇.基于P-Rank的RDF有向图的分布式存储[J].重庆理工大学学报(自然科学),2015,29(1):91-95

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .