Maximizing edge connectivity in graph partitioning using hotspots

Alobaidi, I.; Fareed, H.; Leopold, J.; Smith, A.

Abstract: Graphs have long been used to model relationships between entities. For some applications, a single graph is sufficient; for other problems, a collection of graphs may be more appropriate to represent the underlying data. Many contemporary problem domains, for which graphs are an ideal data model, contain an enormous amount of data (e.g., social networks). Hence, researchers frequently employ parallelized or distributed processing. The graph data must first be partitioned and assigned to the multiple processors in a way that the workload is balanced and inter-processor communication is minimized. The latter problem may be complicated by the existence of edges between vertices in a graph that have been assigned to different processors. Herein we introduce a strategy that combines vocabulary-based summarization of graphs (VoG) and detection of hotspots (i.e., vertices of high degree) to determine how a single undirected graph should be partitioned to optimize multi-processor load balancing and minimize the number of edges that exist between the partitioned subgraphs. We benchmark our method against another well-known partitioning algorithm (METIS) to demonstrate the benefits of our approach.

How to cite this paper

 Alobaidi, I., Fareed, H., Leopold, J & Smith, A. (2025). Maximizing edge connectivity in graph partitioning using hotspots.International Journal of Data and Network Science, 9(3), 385-394.

References

Bonnet, E., Escoffier, B., Paschos, V. T., & Tourniaire, E. (2015). Multi-parameter analysis for local graph partitioning problems: Using greediness for parameterization. Algorithmica, 71(3), 566-580.
Bourse, F., Lelarge, M., & Vojnovic, M. (2014, August). Balanced graph edge partition. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 1456-1465).
Chen, R., Shi, J., Chen, Y., Zang, B., Guan, H., & Chen, H. (2019). Powerlyra: Differentiated graph computation and partitioning on skewed graphs. ACM Transactions on Parallel Computing (TOPC), 5(3), 1-39.
Echbarthi, G., & Kheddouci, H. (2016, August). Streaming METIS partitioning. In 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) (pp. 17-24). IEEE.
G. Karypis (Accessed: 2019-22-01). Complexity of pmetis and kmetis Algorithms. http: //glaros.dtc.umn.edu/gkhome/node/419
Gonzalez, J. E., Low, Y., Gu, H., Bickson, D., & Guestrin, C. (2012). {PowerGraph}: Distributed {Graph-Parallel} computation on natural graphs. In 10th USENIX symposium on operating systems design and implementation (OSDI 12) (pp. 17-30).
Gonzalez, J. E., Xin, R. S., Dave, A., Crankshaw, D., Franklin, M. J., & Stoica, I. (2014). {GraphX}: Graph processing in a distributed dataflow framework. In 11th USENIX symposium on operating systems design and implementation (OSDI 14) (pp. 599-613).
Karypis, G., & Kumar, V. (1998a). A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing, 20(1), 359-392.
Karypis, G., & Kumar, V. (1998b). A parallel algorithm for multilevel graph partitioning and sparse matrix ordering. Journal of parallel and distributed computing, 48(1), 71-95.
Kiveris, R., Lattanzi, S., Mirrokni, V., Rastogi, V., & Vassilvitskii, S. (2014, November). Connected components in mapreduce and beyond. In Proceedings of the ACM Symposium on Cloud Computing (pp. 1-13).
Koutra, D., Kang, U., Vreeken, J., & Faloutsos, C. (2015). Summarizing and understanding large graphs. Statistical Analysis and Data Mining: The ASA Data Science Journal, 8(3), 183-202.
Li, M., Andersen, D. G., & Smola, A. J. (2015). Graph partitioning via parallel submodular approximation to accelerate distributed machine learning. arXiv preprint arXiv:1505.04636.
Park, H. M., Park, N., Myaeng, S. H., & Kang, U. (2016, December). Partition aware connected component computation in distributed systems. In 2016 IEEE 16th International Conference on Data Mining (ICDM) (pp. 420-429). IEEE.
Rahimian, F., Payberah, A. H., Girdzijauskas, S., Jelasity, M., & Haridi, S. (2015). A distributed algorithm for large-scale graph partitioning. ACM Transactions on Autonomous and Adaptive Systems (TAAS), 10(2), 1-24.
Roy, A., Bindschaedler, L., Malicevic, J., & Zwaenepoel, W. (2015, October). Chaos: Scale-out graph processing from secondary storage. In Proceedings of the 25th Symposium on Operating Systems Principles (pp. 410-424).
Sakouhi, C., Khaldi, A., & Ghezal, H. B. (2018). An overview of recent graph partitioning algorithms. In Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA) (pp. 408-414). The Steering Committee of The World Congress in Computer Science, Computer Engineering and Applied Computing (WorldComp).
Verma, S., Leslie L., Shin Y., & Gupta I. (2017). An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing. In Proceedings of the 43rd International Conference on Very Large Data Bases (VLDB) Endowment, vol. 10, no. 5, pp. 493–504.
Wang, L., Xiao, Y., Shao, B., & Wang, H. (2014, March). How to partition a billion-node graph. In 2014 IEEE 30th International Conference on Data Engineering (pp. 568-579). IEEE.
Ward, K., Lin, D., & Madria, S. (2017, June). Melt: Mapreduce-based efficient large-scale trajectory anonymization. In Proceedings of the 29th International Conference on Scientific and Statistical Database Management (pp. 1-6).
Zhang, C., Wei, F., Liu, Q., Tang, Z. G., & Li, Z. (2017, August). Graph edge partitioning via neighborhood heuristic. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 605-614).