nach oben

Cluster Computing

Erschienen in:

23.03.2023

A new distributed graph coloring algorithm for large graphs

verfasst von: Assia Brighen, Hachem Slimani, Abdelmounaam Rezgui, Hamamache Kheddouci

Erschienen in: Cluster Computing | Ausgabe 1/2024

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The vertex graph coloring problem (VGCP) is one of the most well-known problems in graph theory. It is used for solving several real-world problems such as compiler optimization, map coloring, and frequency assignment. The goal of VGCP is to color all vertices of the graph so that adjacent vertices receive different colors and the number of different colors used is minimized. The main difficulty of this problem resides when the graph size increases, that induces the increase in complexity of the VGCP which gives it the characteristic of being an NP-hard problem. To deal with this problem in the context of large graphs, different options are considered, including new large graph parallel processing frameworks such as Pregel, Graphx and Giraph. The latter is viewed as one of the most popular large graph processing frameworks both in industry and academia. In this work, we propose a new parallel graph coloring algorithm, called DistG, based on the vertex-centric computation model. The main feature of the proposed algorithm is that it colors all the vertices in its second superstep, corresponding to the initial coloration stage, and in the other supersteps takes care of conflict correction. And this allows it to exclude from the computation from the third superstep all the vertices not concerned by conflicts, what makes it several important gains in terms of number of supersteps, number of exchanged messages, and execution time. For its implementation, we have used the Giraph framework but it can be easily adaptable to any vertex-centric system. We have evaluated the DistG algorithm on several datasets from the SNAP graph benchmark using a Hadoop Cluster. The obtained results have shown that the proposed algorithm performs better than concurrent algorithms in terms of number of colors, CPU time, number of supersteps, and communication cost.

Vorheriger Artikel A comprehensive analysis for crowd counting methodologies and algorithms in Internet of Things

Nächster Artikel Towards adding digital forensics capabilities in software defined networking based moving target defense

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Abbasian, R., Mouhoub, M.: An efficient hierarchical parallel genetic algorithm for graph coloring problem. In: GECCO’11 Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, pp. 521–528 (2011). https://doi.org/10.1145/2001576.2001648

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

Adeogun, R., Berardinelli, G., Mogensen, P.: Learning to dynamically allocate radio resources in mobile 6g in-x subnetworks. In: 2021 IEEE 32nd Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), pp. 959–965 (2021). https://doi.org/10.1109/PIMRC50174.2021.9569345

Alabandi, G., Powers, E., Burtscher, M.: Increasing the parallelism of graph coloring via shortcutting. In: PPoPP’20, Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 262–275 (2020). https://doi.org/10.1145/3332466.3374519

Aslan, M., Baykan, N.A.: A performance comparison of graph coloring algorithms. Intell. Syst. Appl. Eng. 4(Special Issue–1), 1–7 (2016). https://doi.org/10.18201/ijisae.273053CrossRef

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-9MathSciNetCrossRef

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

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.98MathSciNetCrossRef

Bhatia, V., Rani, R.: A distributed overlapping community detection model for large graphs using autoencoder. Futur. Gener. Comput. Syst. 94, 16–26 (2019). https://doi.org/10.1016/j.future.2018.10.045CrossRef

10.

Bogle, I., Slota, G.M., Boman, E.G., Devine, K.D., Rajamanickam, S.: Parallel graph coloring algorithms for distributed GPU environments. Parallel Comput. 110, 102896 (2022). https://doi.org/10.1016/j.parco.2022.102896MathSciNetCrossRef

11.

Boman, E.G., Bozdag, D., Catalyurek, U., Gebremedhin, A.H., Manne, F.: 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–251 (2005). https://doi.org/10.1007/11549468_29

12.

Bozdağ, D., Gebremedhin, A.H., Manne, F., Boman, E.G., Catalyurek, U.V.: 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.002CrossRef

13.

Brighen, A., Slimani, H., Rezgui, A., Kheddouci, H.: A distributed large graph coloring algorithm on giraph. In: CloudTech’20, the 5th International Conference on Cloud Computing and Artificial Intelligence: Technologies and Applications, Marrakesh, Morocco, pp. 1–7. https://doi.org/10.1109/CloudTech49835.2020.9365872

14.

Brighen, A., Slimani, H., Rezgui, A., Kheddouci, H.: 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-4CrossRef

15.

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

16.

Capelli, L.A.R., Hu, Z., Zakian, T.A.K., Brown, N., Bull, J.M.: iPregel: Vertex-centric programmability vs memory efficiency and performance, why choose? Parallel Comput. 86, 45–56 (2019). https://doi.org/10.1016/j.parco.2019.04.005CrossRef

17.

Chen, H., Zhou, P.: An ant algorithm for solving the four-coloring map problem. In: The Ninth International Conference on Natural Computation (ICNC), pp. 491–495 (2013). https://doi.org/10.1109/ICNC.2013.6818026

18.

Chen, W., Chen, W., Ashar, P., Chen, K., Cheng, B.: 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

19.

Ching, A.: Scaling apache giraph to a trillion edges. Facebook Engineering blog. http://www.facebook.com/10151617006153920 (2013)

20.

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

21.

Deveci, M., Boman, E.G., Devine, K.D., Rajamanickam, S.: Parallel graph coloring for manycore architectures. In: 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, Chicago, IL, USA, pp. 892–901 (2016). https://doi.org/10.1109/IPDPS.2016.54

22.

Gamache, M., Hertz, A., Ouellet, J.O.: A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding. Comput. Oper. Res. 34, 2384–2395 (2007). https://doi.org/10.1016/j.cor.2005.09.010CrossRef

23.

Gandhi, N.M., Misra, R.: Performance comparison of parallel graph coloring algorithms on bsp model using hadoop. In: 2015 International Conference on Computing, Networking and Communications (ICNC), CA, USA, pp. 110–116 (2015). https://doi.org/10.1109/ICCNC.2015.7069325

24.

Gebremedhin, A.H., Manne, F.: Scalable parallel graph coloring algorithms. Concurrency 12(12), 1131–1146 (2000)CrossRef

25.

Giraph, A.: Apache giraph! https://giraph.apache.org

26.

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

27.

Goodarzi, B., Burtscher, M., Goswami, D.: Parallel graph partitioning on a CPU-GPU architecture. In: 2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), Chicago, IL, USA, pp. 58–66 (2016). https://doi.org/10.1109/IPDPSW.2016.16

28.

Grosset, A.V.P., Zhuand, P., Venkatasubramanian, S., Hall, M.: Evaluating graph coloring on GPUs. In: PPoPP’11 Proceedings of the 16th ACM Symposium on Principles and Practice of Parallel Programming, ACM SIGPLAN Notices-PPoPP’11, vol. 46(8), pp. 297–298 (2011). https://doi.org/10.1145/2038037.1941597

29.

Gwee, B.H., Lim, M.H., Ho, J.S.: Solving four-colouring map problem using genetic algorithm. In: The First New Zealand International Two-Stream Conference on Artificial Neural Networks and Expert Systems, pp. 332–333 (1993). https://doi.org/10.1109/ANNES.1993.323010

30.

Hasenplaugh, W., Kaler, T., Schardl, T.B., Leiserson, C.E.: 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

31.

Hendren, L.J., Gao, G.R., Altman, E.R., Mukerji, C.: A register allocation framework based on hierarchical cyclic interval graphs. In: International Conference on Compiler Construction, pp. 176–191 (1992). https://doi.org/10.1007/3-540-55984-1_17

32.

Hertz, A., Ries, B.: A note on r-equitable k-colorings of trees. Yugoslav J. Oper. Res. 24(2), 293–298 (2014). https://doi.org/10.2298/YJOR130704039HMathSciNetCrossRef

33.

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) (2019). https://doi.org/10.1007/978-3-030-19212-9_25

34.

Irving, R.W., Manlove, D.F.: The b-chromatic number of a graph. Discret. Appl. Math. 91(1–3), 127–141 (1999). https://doi.org/10.1016/S0166-218X(98)00146-2CrossRef

35.

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

36.

Karp, R.M.: Reducibility among combinatorial problems. Complex. Comput. Comput., 85–103 (1972). https://doi.org/10.1007/978-1-4684-2001-2_9

37.

Kosowski, A., Manuszewski, K.: Classical graph coloring. In: Kubale, M. (ed.) Graph Colorings, chapter 1, pp. 1–20. American Mathematical Society, Providence (2004)

38.

Leskovec, J., Krevl, A.: Snap datasets: Stanford large network dataset collection. http://snap.stanford.edu/data (2014)

39.

Liu, H.F., Su, C.T., Chu, A.C.: Fast quasi-biclique mining with giraph. In: BIGDATACONGRESS’13 Proceedings of the 2013 IEEE International Congress on Big Data, pp. 347–354 (2013). https://doi.org/10.1109/BigData.Congress.2013.53

40.

Loveless, T., Ott, J., Brisk, P.: A performance-optimizing compiler for cyber-physical digital microfluidic biochips. In: CGO 2020, Proceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization, pp. 171–184 (2020). https://doi.org/10.1145/3368826.3377925

41.

Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036–1053 (1986). https://doi.org/10.1137/0215074MathSciNetCrossRef

42.

Lunagariya, D.C., Somayajulu, D.V.L.N., Krishna, P.R.: 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

43.

Malewicz, G., Austern, M.H., Bik, A.J.C., Dehnert, J.C., Horn, I., Leiser, N., Czajkowski, G.: 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

44.

Patidar, H., Chakrabarti, P.: A tree-based graph coloring algorithm using independent set. In: Progress in Advanced Computing and Intelligent Engineering, pp. 537–546 (2019). https://doi.org/10.1007/978-981-13-0224-4_48

45.

Peng, Y., Choi, B., He, B., Zhou, S., Xu, R., Yu, X.: Vcolor: A practical vertex-cut based approach for coloring large graphs. In: 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pp. 97–108 (2016). https://doi.org/10.1109/ICDE.2016.7498232

46.

Rahman, M.S.: Basic Graph Theory. Springer International Publishing, 1 edn (2017). https://doi.org/10.1007/978-3-319-49475-3

47.

Rai, D., Chaudhari, N.S., Ingle, M.: An efficient algorithmic 3-sat formulation for sudoku puzzle using graph coloring. In: 2018 International Conference on Advanced Computation and Telecommunication (ICACAT), Bhopal, India, pp. 1–6 (2018). https://doi.org/10.1109/ICACAT.2018.8933664

48.

Rajan, A.K., Bhaiya, D.: Accelerated kerninghan lin algorithm for graph partitioning. In: 2017 International Conference on Advances in Computing, Communications and Informatics (ICACCI), Udupi, India, pp. 58–66 (2017). https://doi.org/10.1109/ICACCI.2017.8125836

49.

Ramachandran, T., Deepika, N.: Vertex coloring of graph using adjacency matrix. J. Eng. Resh Appl. 10(4), 1–5 (2020). https://doi.org/10.9790/9622-1004050105CrossRef

50.

Riihijarvi, J., Petrova, M., Mahonen, P.: Frequency allocation for wlans using graph colouring techniques. In: Second Annual Conference on Wireless On-demand Network Systems and Services, pp. 216–222 (2005). https://doi.org/10.1109/WONS.2005.19

51.

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

52.

Sakr, S., Orakzai, F.M., Abdelaziz, I., Khayyat, Z.: Large-Scale Graph Processing Using Apache Giraph, 1 edn. Springer, Berlin (2016). https://doi.org/10.1007/978-3-319-47431-1

53.

Sakr, S., Orakzai, F.M., Abdelaziz, I., Khayyat, Z.: Large-Scale Graph Processing Using Apache Giraph. Springer International Publishing (2016). https://doi.org/10.1007/978-3-319-49475-3

54.

Schuetz, M.J.A., Brubaker, J.K., Zhu, Z., Katzgraber, H.G.: Graph coloring with physics-inspired graph neural networks. arXiv:2202.01606 (2022). https://doi.org/10.48550/arXiv.2202.01606

55.

Shafiq, M., Tian, Z., Sun, Y., Du, X., Guizani, M.: IoT malicious traffic identification using wrapper-based feature selection mechanisms. Comput. Secur. 94, 101863 (2020). https://doi.org/10.1016/j.cose.2020.101863CrossRef

56.

Shafiq, M., Tian, Z., Sun, Y., Du, X., Guizani, M.: Selection of effective machine learning algorithm and Bot-IoT attacks traffic identification for internet of things in smart city. Futur. Gener. Comput. Syst. 107, 433–442 (2020). https://doi.org/10.1016/j.future.2020.02.017CrossRef

57.

Shafiq, M., Tian, Z., Bashir, A.K., Du, X., Guizani, M.: CorrAUC: a malicious Bot-IoT traffic detection method in IoT network using machine-learning techniques. IEEE Internet Things J. 8(5), 3242–3254 (2021). https://doi.org/10.1109/JIOT.2020.3002255CrossRef

58.

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

59.

Shen, Y., Sun, Y., Li, X., Eberhard, A., Ernst, A.: Enhancing column generation by a machine-learning-based pricing heuristic for graph coloring. Proc. AAAI Confer. Artific. Intell. 36(9), 9926–9934 (2022). https://doi.org/10.1609/aaai.v36i9.21230CrossRef

60.

Shukla, A.N., Garg, M.L., Misra, R.: An approach to solve graph coloring problem using linked list. Int. J. Adv. Stud. Sci. Res., 4(2) (2019)

61.

Si, Z., Chuai, G., Gao, W., Zhang, J., Chen, X., Zhang, K.: A QoS-based joint user association and resource allocation scheme in ultra-dense networks. EURASIP J. Wirel. Commun. Netw. 2021(1), 1–24 (2021). https://doi.org/10.1186/s13638-020-01882-3CrossRef

62.

Ait Taleb, S., Slimani, H., Khanouche, M.E.: A routing approach based on (N, p)-equitable b-coloring of graphs for wireless sensor networks. In: 2018 International Conference on Smart Communications in Network Technologies (SaCoNeT), pp. 90–95 (2018). https://doi.org/10.1109/SaCoNeT.2018.8585585

63.

Ait Taleb, S., Slimani, H., Kheddouci, H.: (n, p)-equitable b-coloring of graphs. Discret. Appl. Math. 235, 1–5 (2018). https://doi.org/10.1016/j.dam.2017.09.004CrossRef

64.

Tziritas, N., Loukopoulos, T., Khan, S.U., Xu, C., Zomaya, A.Y.: A communication-aware energy-efficient graph coloring algorithm for vm placement in clouds. In: 2018 IEEE SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computing, Scalable Computing & Communications, Cloud & Big Data Computing, Internet of People and Smart City Innovation (SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI), pp. 1684–1691 (2018). https://doi.org/10.1109/SmartWorld.2018.00286

65.

Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103–111 (1990). https://doi.org/10.1145/79173.79181CrossRef

66.

Vizing, V.G.: Some unsolved problems in graph theory. Russ. Math. Surv. 23(6), 125–141 (1968). https://doi.org/10.1070/RM1968v023n06ABEH001252MathSciNetCrossRef

67.

Welsh, D.J.A., Powell, M.B.: 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.85CrossRef

68.

Xin, R.S., Gonzalez, J.E., Franklin, M.J., Stoica, I.: Graphx: a resilient distributed graph system on spark. In: GRADES’13 First International Workshop on Graph Data Management Experiences and Systems, Article No. 2 (2013). https://doi.org/10.1145/2484425.2484427

69.

Yadav, J.R., Somayajulu, D.V.L.N., Krishna, P.R.: A scalable algorithm for discovering topologies in social networks. In: 2014 IEEE International Conference on Data Mining Workshop, Shenzhen, China, pp. 818–827 (2014). https://doi.org/10.1109/ICDMW.2014.75

70.

Zhaocai, W., Dangweia, W., Xiaoguangb, B., Tunhua, W.: A parallel biological computing algorithm to solve the vertex coloring problem with polynomial time complexity. Journal of Intelligent & Fuzzy Systems, pages 1–11, (2021). https://doi.org/10.3233/JIFS-200025

71.

Zheng, Z., Shi, X., He, L., Jin, H., Wei, S., Dai, H., Peng, X.: Feluca: a two-stage graph coloring algorithm with color-centric paradigm on GPU. IEEE Trans. Parallel Distrib. Syst. 32(1), 160–173 (2020). https://doi.org/10.1109/TPDS.2020.3014173CrossRef

Titel: A new distributed graph coloring algorithm for large graphs
verfasst von: Assia Brighen
Hachem Slimani
Abdelmounaam Rezgui
Hamamache Kheddouci
Publikationsdatum: 23.03.2023
Verlag: Springer US
Erschienen in: Cluster Computing / Ausgabe 1/2024
Print ISSN: 1386-7857
Elektronische ISSN: 1573-7543
DOI: https://doi.org/10.1007/s10586-023-03988-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2024

Redundancy elimination in IoT oriented big data: a survey, schemes, open challenges and future applications

Machine learning regression-based RETRO-VLP for real-time and stabilized indoor positioning

Heuristic algorithm for task mapping problem in a hierarchical wireless network-on-chip architecture

Parallel multi-GPU implementation of fast decoupled power flow solver with hybrid architecture

An efficient document information retrieval using hybrid global search optimization algorithm with density based clustering technique

Multi-input cloud resource allocation strategy with limited buffer and virtual machine synchronization failure

Premium Partner