[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Giraph-Based Distributed Algorithms for Coloring Large-Scale Graphs

  • Published:
International Journal of Parallel Programming Aims and scope Submit manuscript

Abstract

The Vertex Graph Coloring problem (\(\mathcal {VGC}\)) is a well-known difficult combinatorial optimization problem. It is one of Karp’s 21 NP-complete problems. It consists in assigning a color to each vertex of a graph in such a way that any two neighboring vertices do not share the same color, and the number of the used colors is minimized. \(\mathcal {VGC}\) is used to solve a variety of real-world problems such as time tabling and scheduling, radio frequency assignment, and computer register allocation. To deal with this problem on large graphs, the emerging large graph processing frameworks are an excellent promising candidate. Giraph is one of the most popular large graph processing frameworks both in industry and academia. In this work, two novel graph coloring algorithms are introduced. These algorithms designed to reap the benefit of the simple parallelization model offered by any vertex-centric frameworks, such as Giraph. The algorithms are based on well-known sequential heuristic techniques namely Largest-First (LF) and Saturation Largest-First (SLF). We have compared the performances of the proposed algorithms to previous Giraph based graph coloring algorithms, with regard to their solution quality and executing time, using benchmark graphs from the SNAP library. The obtained experimental results have revealed that the proposed algorithms are much more efficient than the existing Giraph algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Algorithm 1
Algorithm 2
Fig. 2
Fig. 3
Fig. 4
Algorithm 3
Algorithm 4
Algorithm 5
Algorithm 6
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Data Availability

The used Dataset is publically accessible via http://snap.stanford.edu/data

References

  1. Acer, S., Boman, E., Glusa, Ch.A., et al.: Sphynx: a parallel multi-GPU graph partitioner for distributed-memory systems. Parallel. Comput. 106, 102769 (2021). https://doi.org/10.1016/j.parco.2021.102769

    Article  MathSciNet  Google Scholar 

  2. Aslan, M., Baykan, N.: A performance comparison of graph coloring algorithms. In: ICAT’2016, 3rd International conference on advanced technology & Sciences, Konya, Turkey (2016)

  3. Avanthay, C., Hertz, A., Zufferey, N.: A variable neighborhood search for graph coloring. Eur. J. Oper. Res. 151(2), 379–388 (2003). https://doi.org/10.1016/S0377-2217(02)00832-9

    Article  MathSciNet  Google Scholar 

  4. Avery, C.: Giraph: large-scale graph processing infrastructure on hadoop. In: Proceeding of the 2011 Hadoop Summit Santa Clara (2011)

  5. Barnier, N., Brisset, P.: Graph coloring for air traffic flow management. Ann. Oper. Res. 130(1–4), 163–178 (2004). https://doi.org/10.1023/B:ANOR.0000032574.01332.98

    Article  MathSciNet  Google Scholar 

  6. Bogle, I., Slota, G., Boman, E., et al.: Parallel graph coloring algorithms for distributed GPU environments. Parallel Comput. 110, 102896 (2022). https://doi.org/10.1016/j.parco.2022.102896

    Article  MathSciNet  Google Scholar 

  7. Boman, E., Bozdag, D., Catalyurek, U., et al.: A scalable parallel graph coloring algorithm for distributed memory computers. In: Euro-Par’05 Proceedings of the 11th international Euro-Par conference on parallel processing pp 241–25 (2005) https://doi.org/10.1007/11549468_29

  8. Bozdag, D., Gebremedhin, A., Manne, F., et al.: A framework for scalable greedy coloring on distributed-memory parallel computers. J. Parallel Distrib. Comput. 68(4), 515–535 (2008). https://doi.org/10.1016/j.jpdc.2007.08.002

    Article  Google Scholar 

  9. Bravyi, S., Kliesch, A., Koenig, R., et al.: Hybrid quantum-classical algorithms for approximate graph coloring. Quantum 6, 678 (2022). https://doi.org/10.22331/q-2022-03-30-678

    Article  Google Scholar 

  10. Brighen, A., Slimani, H., Rezgui, A., et al.: Listing all maximal cliques in large graphs on vertex-centric model. J Supercomput. 75, 4918–4946 (2019). https://doi.org/10.1007/s11227-019-02770-4

    Article  Google Scholar 

  11. Brighen, A., Slimani, H., Rezgui, A., et al.: A distributed large graph coloring algorithm on giraph. In: 2020 5th International conference on cloud computing and artificial intelligence: technologies and applications (CloudTech), Marrakesh, Morocco pp 1– (2020) https://doi.org/10.1109/CloudTech49835.2020.9365872

  12. Brighen, A., Slimani, H., Rezgui, A., et al.: A new distributed graph coloring algorithm for large graphs. Cluster Comput. 27(1), 875–891 (2024). https://doi.org/10.1007/s10586-023-03988-x

    Article  Google Scholar 

  13. Bré1az D,: New methods to color the vertices of a graph. Commun. ACM 22(4), 251–256 (1979). https://doi.org/10.1145/359094.359101

  14. Chen, H., Zhou, P.: An ant algorithm for solving the four-coloring map problem. In: The 9th international conference on natural computation (ICNC) pp 491–495 (2013) https://doi.org/10.1109/ICNC.2013.6818026

  15. Chen, W., Chen, W., Ashar, P., et al.: Register allocation for intel processor graphics. In: CGO 2018 Proceedings of the 2018 International symposium on code generation and optimization pp 352–364 (2018) https://doi.org/10.1145/3168806

  16. Deveci, M., Boman, E., Devine, K., et al.: Parallel graph coloring for manycore architectures. In: 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS) pp 892–901 (2016) https://doi.org/10.1109/IPDPS.2016.54

  17. Gandhi, N., Misra, R.: Performance comparison of parallel graph coloring algorithms on bsp model using hadoop. In: 2015 International conference on computing, networking and communications, USA pp 110–116. (2015) https://doi.org/10.1109/ICCNC.2015.7069325

  18. Gebremedhin, A., Manne, F.: Scalable parallel graph coloring algorithms. Concurr. Comput. 12(12), 1131–1146 (2000)

    Google Scholar 

  19. Giraph A (Accessed 01 Mars 2023) Apache giraph! https://giraph.apache.org

  20. Gjertsen, J., Jones, M.T., Plassmann, P.: Parallel heuristics for improved, balanced graph colorings. J. Parallel Distrib. Comput. 37(2), 171–186 (1996). https://doi.org/10.1006/jpdc.1996.0117

    Article  Google Scholar 

  21. Gross, J., Yellen, J., Zhang, P.: Handbook of graph theory, 2nd edn. CRC Press Taylor & Francis Group (2014)

  22. Hasenplaugh W, Kaler T, Schardl T, et al.: Ordering heuristics for parallel graph coloring. In: SPAA’14: Proceedings of the 26th ACM symposium on parallelism in algorithms and architectures pp. 166–177. (2014) https://doi.org/10.1145/2612669.2612697

  23. Hertz, A., de Werra, D.: Using tabu search techniques for graph coloring. J Comput 39(4), 345–35 (1987). https://doi.org/10.1007/BF02239976

    Article  MathSciNet  Google Scholar 

  24. Holtfort, T., Horsch, A.: Social science goes quantum: explaining human decision-making, cognitive biases and darwinian selection from a quantum perspective. J Bioeconomics. 25, 99–116 (2023). https://doi.org/10.1007/s10818-023-09334-w

    Article  Google Scholar 

  25. Hébrard E, Katsirelos G.: A hybrid approach for exact coloring of massive graphs. In: International conference on integration of constraint programming, artificial intelligence, and operations research (CPAIOR 2019) pp 374–39 (2019) https://doi.org/10.1007/978-3-030-19212-9_25

  26. Jones, M., Plassmann, P.: A parallel graph coloring heuristic. SIAM J. Sci. Comput. 14(3), 654–669 (1993). https://doi.org/10.1137/0914041

    Article  MathSciNet  Google Scholar 

  27. Karp, R.: Reducibility among combinatorial problems. complexity of computer computations pp 85–10 (1972) https://doi.org/10.1007/978-1-4684-2001-2_9

  28. Kosowski, A., Manuszewski, K.: Classical graph coloring, In: Kubale, M. (ed.) Graph colorings, American mathematical society, Providence, chap 1, pp 1–20 (2004)

  29. Leskovec, J., Krevl, A.: ((Accessed 01 Mars 2023)) Snap datasets: stanford large network dataset collection. (2014) http://snap.stanford.edu/data

  30. Liu, H., Su, C., Chu, A.: Fast quasi-biclique mining with giraph. In: BIGDATACONGRESS’13 Proceedings of the 2013 IEEE international congress on big data pp 347–3 (2013) https://doi.org/10.1109/BigData.Congress.2013.53

  31. Luby M .: A simple parallel algorithm for the maximal independent set problem. In: Proceedings of the 17th annual ACM symposium on theory of computing 15(4):1036–1053 (1986) https://doi.org/10.1145/22145.22146

  32. Lucet, C., Mendes, F., Moukrim, A.: An exact method for graph coloring. Comput. Oper. Res. 33(8), 2189–2207 (2006). https://doi.org/10.1016/j.cor.2005.01.008

    Article  MathSciNet  Google Scholar 

  33. Lunagariya, D., Somayajulu, D., Krishna, P.: Se-cda: A scalable and efficient community detection algorithm. In: 2014 IEEE international conference on big data (big data), Washington, DC, USA pp 877–882. (2014) https://doi.org/10.1109/BigData.2014.7004318

  34. Malewicz G, Austern M, Bik A, et al.: Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD International conference on management of data, Indiana, USA pp 135–146. (2010) https://doi.org/10.1145/1807167.1807184

  35. Malhotra, K., Vasa, K.D., Chaudhary, N., et al.: A solution to graph coloring problem using genetic algorithm. EAI Endorsed Trans. Scalable Info. Syst. (2024). https://doi.org/10.4108/eetsis.5437

    Article  Google Scholar 

  36. Ogunkan, S., Idowu, P., Omidiora, E., et al.: First fit algorithm: a graph coloring approach to conflict-free university course timetabling. Asian J. Res. Comput. Sci. 17(5), 125–139 (2024). https://doi.org/10.9734/AJRCOS/2024/v17i5443

    Article  Google Scholar 

  37. Pardalos, P., Mavridou, T., Xue, J.: The graph coloring problem: a bibliographic survey. Handb. Comb. Optim. 2, 331–395 (1998). https://doi.org/10.1016/j.neucom.2023.126631

    Article  MathSciNet  Google Scholar 

  38. Patidar, H., Chakrabarti, P.: A tree-based graph coloring algorithm using independent set. In: Progress in advanced computing and intelligent engineering: Proceedings of ICACIE 2017, 537–546 (2019). https://doi.org/10.1007/978-981-13-0224-4_48

  39. Rahman M.: Basic graph theory, 1st edn. Springer (2017) https://doi.org/10.1007/978-3-319-49475-3

  40. Rajan A, Bhaiya D.: Accelerated kerninghan lin algorithm for graph partitioning. In: 2017 International conference on advances in computing, communications and informatics, India pp 58–66. (2017) https://doi.org/10.1109/ICACCI.2017.8125836

  41. Roy, S., Dey, P., Kundu, D.: Social network analysis of cricket community using a composite distributed framework: from implementation viewpoint. IEEE Trans. Comput. Soc. Syst. 5(1), 64–81 (2018). https://doi.org/10.1109/TCSS.2017.2762430

    Article  Google Scholar 

  42. Sakr S, Orakzai F, Abdelaziz I, et al.: Large-Scale graph processing using Apache Giraph, 1st edn. Springer (2016) https://doi.org/10.1007/978-3-319-47431-1

  43. Shao Y, Chen L, Cui B .: Efficient cohesive subgraphs detection in parallel. In: SIGMOD’14 Proceedings of the 2014 ACM SIGMOD international conference on management of data , Utah, USA pp 613–624. (2014) https://doi.org/10.1145/2588555.2593665

  44. Shukla A, Garg M, Misra R.: An approach to solve graph coloring problem using linked list. IJASSR 4(2) (2019)

  45. Sun, W., Hao, J., Zang, Y., et al.: A solution-driven multilevel approach for graph coloring. Appl. Soft. Comput. 104, 10717 (2021). https://doi.org/10.1016/j.asoc.2021.107174

    Article  Google Scholar 

  46. Welsh, D., Powell, M.: An upper bound for the chromatic number of a graph and its application to timetabling problems. Comput. J 10(1), 85–86 (1967). https://doi.org/10.1093/comjnl/10.1.85

    Article  Google Scholar 

  47. de Werra, D., Gay, Y.: Chromatic scheduling and frequency assignment. Discrete Appl. Math. 49(1–3), 165–174 (1994). https://doi.org/10.1016/0166-218X(94)90207-0

    Article  MathSciNet  Google Scholar 

  48. Xin R, Gonzalez J, Franklin M, et al .: Graphx: a resilient distributed graph system on spark. In: GRADES’13 1st International workshop on graph data management experiences and systems pp 1–6 . (2013) https://doi.org/10.1145/2484425.2484427

  49. Zhou, Z., Li, C., Huang, C., et al.: An exact algorithm with learning for the graph coloring problem. Comput. Oper. Res. 51, 282–301 (2014). https://doi.org/10.1016/j.cor.2014.05.017

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgment

The authors are thankful to the anonymous referees for their valuable suggestions and comments which have helped to improve the quality of the paper.

Funding

No funding

Author information

Authors and Affiliations

  1. LIMED Laboratory, Faculty of Exact Sciences, University of Bejaia, 06000, Bejaia, Algeria

    Assia Brighen & Hachem Slimani

  2. Computer Science Department, University of Jijel, 18000, Jijel, Algeria

    Assia Brighen, Asma Chouikh & Hamida Ikhlef

  3. School of Information Technology, Illinois State University, Normal, IL, USA

    Abdelmounaam Rezgui

  4. CNRS, Université Lyon 1, LIRIS, Université de Lyon, Lyon, France

    Hamamache Kheddouci

Authors
  1. Assia Brighen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Asma Chouikh
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Hamida Ikhlef
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Hachem Slimani
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Abdelmounaam Rezgui
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Hamamache Kheddouci
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors have examined, approved, and confirmed the manuscript and have contributed significantly to the manuscript. All authors of this article have read, reviewed, and approved the current version of this work.

Corresponding author

Correspondence to Assia Brighen.

Ethics declarations

Conflict of interest

The authors proclaim that they have no Conflict of interest as specified by Springer, or other interests that might be perceived to influence the results and/or discussion reported in this manuscript.

Ethical Approval

Ethical approval is not required, since this manuscript does not include any studies with human or animal subjects.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Brighen, A., Chouikh, A., Ikhlef, H. et al. Giraph-Based Distributed Algorithms for Coloring Large-Scale Graphs. Int J Parallel Prog 53, 1 (2025). https://doi.org/10.1007/s10766-024-00781-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10766-024-00781-0

Keywords

Search

Navigation