| Peer-Reviewed

An Overview of Metrics for Evaluating the Quality of Graph Partitioners

Received: 12 January 2022     Accepted: 3 February 2022     Published: 16 February 2022
Views:       Downloads:
Abstract

Nowadays, many applications that involve big data can be modelled as graphs. In many cases these graphs may be too large to be loaded and processed on a single commodity computer. This necessitated the development of frameworks that allow processing large graphs by distributing the graph among nodes in a cluster. To process a graph using these frameworks, first, the graph is partitioned into smaller components called subgraphs or partitions, and then assign these smaller subgraphs to different nodes for parallel processing. Depending on the type of processing (example, computing pagerank, counting number of triangles etc.), there will be some communication between nodes during the execution, this communication affects execution time. Therefore, graph partitioning is an important step in distributed graph processing. Being able to determine the quality of a partition prior to processing is important as this will allow us to predict the execution time before the actual processing. A number of metrics for evaluating the quality of a graph partitions exist, but studies show that these metrics may not serve as accurate predictors in many cases. In this work, we reviewed published papers about graph partitioning and we were able to identify and defined more metrics in order to have a catalogue of these metrics.

Published in Mathematics and Computer Science (Volume 7, Issue 1)
DOI 10.11648/j.mcs.20220701.11
Page(s) 1-8
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2022. Published by Science Publishing Group

Keywords

Graph, Graph Partitioning, Partitioning Algorithms, Metrics

References
[1] L. Wang, Y. Xiao, B. Shao, and H. Wang, “How to partition a billion-node graph,” in 2014 IEEE 30th International Conference on Data Engineering, 2014, no. 20100071120032, pp. 568–579.
[2] A. Ching, S. Edunov, M. Kabiljo, D. Logothetis, and S. Muthukrishnan, “One trillion edges,” Proc. VLDB Endow., vol. 8, no. 12, pp. 1804–1815, Aug. 2015.
[3] A. Kyrola, G. Blelloch, and C. Guestrin, “GraphChi,” USENIX Symp. Oper. Syst. Des. Implement., vol. 10, no. 31, pp. 31–46, 2012.
[4] H. Mykhailenko, G. Neglia, and F. Huet, “Which metrics for vertex-cut partitioning?,” in 2016 11th International Conference for Internet Technology and Secured Transactions (ICITST), 2016, pp. 74–79.
[5] F. Rahimian, A. H. Payberah, S. Girdzijauskas, M. Jelasity, and S. Haridi, “A Distributed Algorithm for Large-Scale Graph Partitioning,” ACM Trans. Auton. Adapt. Syst., vol. 10, no. 2, pp. 1–24, Jun. 2015.
[6] H. Mykhailenko, F. Huet, and G. Neglia, “Comparison of Edge Partitioners for Graph Processing,” in 2016 International Conference on Computational Science and Computational Intelligence (CSCI), 2016, pp. 441–446.
[7] J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin, “PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs,” in Presented as part of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12), 2012, vol. 12, pp. 17–30.
[8] H. P. Sajjad, A. H. Payberah, F. Rahimian, V. Vlassov, and S. Haridi, “Boosting Vertex-Cut Partitioning for Streaming Graphs,” in 2016 IEEE International Congress on Big Data (BigData Congress), 2016, pp. 1–8.
[9] C. Xie, W.-J. Li, and Z. Zhang, “S-PowerGraph: Streaming Graph Partitioning for Natural Graphs by Vertex-Cut,” Nov. 2015.
[10] Spark, “GraphX Programming Guide,” GraphX - Spark 3.2.0 Documentation. [Online]. Available: https://spark.apache.org/docs/latest/graphx-programming-guide.html. [Accessed: 27-Jan-2022].
[11] M. Kim and K. S. Candan, “SBV-Cut: Vertex-cut based graph partitioning using structural balance vertices,” Data Knowl. Eng., vol. 72, pp. 285–303, Feb. 2012.
[12] R. Chen, J. Shi, Y. Chen, B. Zang, H. Guan, and H. Chen, “PowerLyra,” ACM Trans. Parallel Comput., vol. 5, no. 3, pp. 1–39, Jan. 2019.
[13] D. Zheng, D. Mhembere, R. Burns, J. Vogelstein, C. E. Priebe, and A. S. Szalay, “FlashGraph: Processing Billion-Node Graphs on an Array of Commodity SSDs,” Proc. 13th USENIX Conf. File Storage Technol. FAST 2015, pp. 45–58, Aug. 2014.
[14] H. Meyerhenke, B. Monien, and T. Sauerwald, “A new diffusion-based multilevel algorithm for computing graph partitions of very high quality,” in 2008 IEEE International Symposium on Parallel and Distributed Processing, 2008, vol. 69, no. 9, pp. 1–13.
[15] B. Hendrickson and T. G. Kolda, “Graph partitioning models for parallel computing,” Parallel Comput., vol. 26, no. 12, pp. 1519–1534, Nov. 2000.
[16] C. Tsourakakis, C. Gkantsidis, B. Radunovic, and M. Vojnovic, “FENNEL,” in Proceedings of the 7th ACM international conference on Web search and data mining, 2014, pp. 333–342.
[17] C. Martella, D. Logothetis, A. Loukas, and G. Siganos, “Spinner: Scalable Graph Partitioning in the Cloud,” in 2017 IEEE 33rd International Conference on Data Engineering (ICDE), 2017, vol. 26, no. 12, pp. 1083–1094.
Cite This Article
  • APA Style

    Mustapha Abdulkadir Sani, Abdulmalik Ahmad Lawan, Ayaz Khalid Mohammed, Abdulkadir Ahmad, Yusuf Haruna. (2022). An Overview of Metrics for Evaluating the Quality of Graph Partitioners. Mathematics and Computer Science, 7(1), 1-8. https://doi.org/10.11648/j.mcs.20220701.11

    Copy | Download

    ACS Style

    Mustapha Abdulkadir Sani; Abdulmalik Ahmad Lawan; Ayaz Khalid Mohammed; Abdulkadir Ahmad; Yusuf Haruna. An Overview of Metrics for Evaluating the Quality of Graph Partitioners. Math. Comput. Sci. 2022, 7(1), 1-8. doi: 10.11648/j.mcs.20220701.11

    Copy | Download

    AMA Style

    Mustapha Abdulkadir Sani, Abdulmalik Ahmad Lawan, Ayaz Khalid Mohammed, Abdulkadir Ahmad, Yusuf Haruna. An Overview of Metrics for Evaluating the Quality of Graph Partitioners. Math Comput Sci. 2022;7(1):1-8. doi: 10.11648/j.mcs.20220701.11

    Copy | Download

  • @article{10.11648/j.mcs.20220701.11,
      author = {Mustapha Abdulkadir Sani and Abdulmalik Ahmad Lawan and Ayaz Khalid Mohammed and Abdulkadir Ahmad and Yusuf Haruna},
      title = {An Overview of Metrics for Evaluating the Quality of Graph Partitioners},
      journal = {Mathematics and Computer Science},
      volume = {7},
      number = {1},
      pages = {1-8},
      doi = {10.11648/j.mcs.20220701.11},
      url = {https://doi.org/10.11648/j.mcs.20220701.11},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.mcs.20220701.11},
      abstract = {Nowadays, many applications that involve big data can be modelled as graphs. In many cases these graphs may be too large to be loaded and processed on a single commodity computer. This necessitated the development of frameworks that allow processing large graphs by distributing the graph among nodes in a cluster. To process a graph using these frameworks, first, the graph is partitioned into smaller components called subgraphs or partitions, and then assign these smaller subgraphs to different nodes for parallel processing. Depending on the type of processing (example, computing pagerank, counting number of triangles etc.), there will be some communication between nodes during the execution, this communication affects execution time. Therefore, graph partitioning is an important step in distributed graph processing. Being able to determine the quality of a partition prior to processing is important as this will allow us to predict the execution time before the actual processing. A number of metrics for evaluating the quality of a graph partitions exist, but studies show that these metrics may not serve as accurate predictors in many cases. In this work, we reviewed published papers about graph partitioning and we were able to identify and defined more metrics in order to have a catalogue of these metrics.},
     year = {2022}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - An Overview of Metrics for Evaluating the Quality of Graph Partitioners
    AU  - Mustapha Abdulkadir Sani
    AU  - Abdulmalik Ahmad Lawan
    AU  - Ayaz Khalid Mohammed
    AU  - Abdulkadir Ahmad
    AU  - Yusuf Haruna
    Y1  - 2022/02/16
    PY  - 2022
    N1  - https://doi.org/10.11648/j.mcs.20220701.11
    DO  - 10.11648/j.mcs.20220701.11
    T2  - Mathematics and Computer Science
    JF  - Mathematics and Computer Science
    JO  - Mathematics and Computer Science
    SP  - 1
    EP  - 8
    PB  - Science Publishing Group
    SN  - 2575-6028
    UR  - https://doi.org/10.11648/j.mcs.20220701.11
    AB  - Nowadays, many applications that involve big data can be modelled as graphs. In many cases these graphs may be too large to be loaded and processed on a single commodity computer. This necessitated the development of frameworks that allow processing large graphs by distributing the graph among nodes in a cluster. To process a graph using these frameworks, first, the graph is partitioned into smaller components called subgraphs or partitions, and then assign these smaller subgraphs to different nodes for parallel processing. Depending on the type of processing (example, computing pagerank, counting number of triangles etc.), there will be some communication between nodes during the execution, this communication affects execution time. Therefore, graph partitioning is an important step in distributed graph processing. Being able to determine the quality of a partition prior to processing is important as this will allow us to predict the execution time before the actual processing. A number of metrics for evaluating the quality of a graph partitions exist, but studies show that these metrics may not serve as accurate predictors in many cases. In this work, we reviewed published papers about graph partitioning and we were able to identify and defined more metrics in order to have a catalogue of these metrics.
    VL  - 7
    IS  - 1
    ER  - 

    Copy | Download

Author Information
  • Department of Computer Science, Kano University of Science and Technology, Wudil, Nigeria

  • Department of Computer Science, Kano University of Science and Technology, Wudil, Nigeria

  • Department of Computer Science, University of Zakho, Kurdistan, Iraq

  • Department of Computer Science, Kano University of Science and Technology, Wudil, Nigeria

  • Department of Computer Science, Kano University of Science and Technology, Wudil, Nigeria

  • Sections