An Overview of Metrics for Evaluating the Quality of Graph Partitioners

Mustapha Abdulkadir Sani; Abdulmalik Ahmad Lawan; Ayaz Khalid Mohammed; Abdulkadir Ahmad; Yusuf Haruna

doi:doi:10.11648/j.mcs.20220701.11

| Peer-Reviewed

An Overview of Metrics for Evaluating the Quality of Graph Partitioners

Mustapha Abdulkadir Sani, Abdulmalik Ahmad Lawan, Ayaz Khalid Mohammed, Abdulkadir Ahmad, Yusuf Haruna

Published in Mathematics and Computer Science (Volume 7, Issue 1)

Received: 12 January 2022 Accepted: 3 February 2022 Published: 16 February 2022

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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

Plain Text BibTeX RIS

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

Mustapha Abdulkadir Sani

Department of Computer Science, Kano University of Science and Technology, Wudil, Nigeria
Abdulmalik Ahmad Lawan

Department of Computer Science, Kano University of Science and Technology, Wudil, Nigeria
Ayaz Khalid Mohammed

Department of Computer Science, University of Zakho, Kurdistan, Iraq
Abdulkadir Ahmad

Department of Computer Science, Kano University of Science and Technology, Wudil, Nigeria
Yusuf Haruna

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

Download PDF

Sections

Plain Text BibTeX RIS

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