Abstract
Distributed graph computing aims at performing in-depth analysis on large networks in a parallel manner. Iterative communication computation is an important model to perform graph analysis. Moreover, high-efficiency iterative communication computation is necessary for assuring the quality of graph partitioning. Many strategies to improve graph computing are usually based on the hypothesis of single communication iteration which focuses on the optimization of load balance in a single graph partitioning and the improvement of parallel granularity or communication manners. However, a graph in the real-world usually requires complex communication iterations to achieve good analysis results, which often have the problems of data and communication tilting and low analysis efficiency. In this paper, we propose a two-stage graph computing model with communication equilibrium (TSMCE). The model employs a communication-equilibrated graph partitioning strategy (CEGP) for load balancing and a two-stage graph computing mode (TS) to reduce the crossing-partition communication. With the change of graph density, various factors such as load balancing, communication balancing, cross-partition transmission traffic, communication delay, and convergence speed can always maintain an efficient balance. The experiments conducted on the real-world datasets show that the communication-equilibrated graph partitioning strategy can divide a graph with high quality compared with Hash and Metis. Besides, the overall performance of our two-stage graph computing model with communication equilibrium is higher than that of the BSP model.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103–111 (1990)
Malewicz, G., et al.: Pregel: a system for large-scale graph processing. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 2010), pp. 135–146. Indianapolis (2010)
Zhang, W.D., Cui, C.: Delta-stepping synchronous parallel model. J. Softw. 30(12), 3622–3636 (2019)
Khorasani, F., Vora, K., Gupta, R., Bhuyan, L.N.: PowerGraph: distributed graph-parallel computation on natural graphs. Oper. Syst. Des. Implementation 17–30 (2012)
Low, Y., Gonzalez, J.E., Kyrola, A., Bickson, D., Guestrin, C.E., Hellerstein, J.: Graphlab: a new framework for parallel machine learning. Comput. Sci. (2014)
Khorasani, F., Vora, K., Gupta, R., Bhuyan, L.N.: CuSha: vertex-centric graph processing on GPUs. High Performance Distrib. Comput. 239–252 (2014)
Reynold, S., Xin, J.E., Gonzalez, M.J., Franklin, I.S.: GraphX: a resilient distributed graph system on spark. In: Proceedings of the 1st International Workshop on Graph Data Management Experiences and Systems (GRADES 2013), pp. 1–6. ACM, New York (2013)
Salihoglu, S., Shin, J., Khanna, V., Truong, B., Widom, J.: Graft: a debugging tool for Apache Giraph. In: Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 2015), pp. 1403–1408. ACM, Melbourne (2015)
Bu, Y., Borkar, V., Jia, J., Carey, M.J., Condie, T.: Pregelix: Big(ger) graph analytics on a dataflow engine. Very Large Data Bases 8(2), 161–172 (2014)
Liu, F.A., Liu, Z.Y., Qiao, X.Z.: An asynchronous BSP model and optimization techniques. Chinese J. Comput. 25(004), 373–380 (2002)
Zhao, X., Li, B., Shang, H.C., Xiao, W.D.: A revised BSP-based massive graph computation model. Chinese J. Comput. 40(01), 223–235 (2017)
Zhang, W., Zhang, M.: Graph partitioning algorithm with LSH: poster extended abstract. In: 2018 IEEE International Conference on Cluster Computing (CLUSTER), pp. 166–167. International Conference on Cluster Computing, Belfast (2018)
Liu, Q., Dong, X., Chen, H., Zhang, X.: H2Pregel: a partition-based hybrid hierarchical graph computation approach. Futur. Gener. Comput. Syst. 104, 15–31 (2020)
Xiao, W., et al.: Distributed graph computation meets machine learning. IEEE Trans. Parallel Distrib. Syst. 31(7), 1588–1604 (2020)
Heintz, B., Hong, R., Singh, S., Khandelwal, G., Tesdahl, C., Chandra, A. MESH: a flexible distributed hypergraph processing system. In: 7th IEEE International Conference on Cloud Engineering (IEEE IC2E), pp. 12–22, International Conference on Cloud Engineering, Prague (2019)
Ji, S., Zhao, Y.A.: Local approximation approach for processing time-evolving graphs. Symmetry 10(7), 2073–8994 (2018)
Heidari, S., Simmhan, Y., Calheiros, R.N., Buyya, R.: Scalable graph processing frameworks: a taxonomy and open challenges. ACM Comput. Surv. 51(3), 1–53 (2018)
Redekopp, M., Simmhan, Y., Prasanna, V.K.: Optimizations and analysis of BSP graph processing models on public clouds. In: 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 203–214. International Parallel and Distributed Processing Symposium, Boston (2013)
Lai, S., Lai, G., Lu, F., Shen, G., Jin, J., Lin, X.: A BSP model graph processing system on many cores. Clust. Comput. 20(2), 1359–1377 (2017). https://doi.org/10.1007/s10586-017-0829-0
Heintz, B., Hong, R.., Singh, S., Khandelwal, G., Tesdahl, C., Chandra, A.: MESH: a flexible distributed hypergraph processing system. In: 7th IEEE International Conference on Cloud Engineering (IEEE IC2E), pp. 12–22. International Conference on Cloud Engineering, Prague (2019)
Karypis, G., Kumar, V.: METIS, a Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-in Reducing Ordering of Sparse Matrices Version 4.0. Department of Computer Science, pp. 44–78, University of Minnesota, Minneapolis (1998)
Stanford University. https://snap.stanford.edu/data/index.html. Accessed 03 June 2020
Ahn, Y., Bagrow, J.P., Lehmann, S.: Link communities reveal multiscale complexity in networks. Nature 466(7307), 761–764 (2010)
Gregory, S.: Finding overlapping communities in networks by label propagation. New J. Phys. 12(10) (2010)
Acknowledgement
This work is partly supported by the National Natural Science Foundation of China under Grant No. 61672159, No. 61672158 and No. 61300104, the Fujian Collaborative Innovation Center for Big Data Applications in Governments, the Fujian Industry-Academy Cooperation Project under Grant No. 2017H6008 and No. 2018H6010, the Natural Science Foundation of Fujian Province under Grant No. 2019J01835 and Haixi Government Big Data Application Cooperative Innovation Center.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Dong, Y., Chen, R., Guo, K. (2021). A Two-Stage Graph Computation Model with Communication Equilibrium. In: Sun, Y., Liu, D., Liao, H., Fan, H., Gao, L. (eds) Computer Supported Cooperative Work and Social Computing. ChineseCSCW 2020. Communications in Computer and Information Science, vol 1330. Springer, Singapore. https://doi.org/10.1007/978-981-16-2540-4_29
Download citation
DOI: https://doi.org/10.1007/978-981-16-2540-4_29
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-16-2539-8
Online ISBN: 978-981-16-2540-4
eBook Packages: Computer ScienceComputer Science (R0)
