nach oben

The Journal of Supercomputing

Erschienen in:

12.02.2019

Listing all maximal cliques in large graphs on vertex-centric model

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

Erschienen in: The Journal of Supercomputing | Ausgabe 8/2019

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Maximal Clique Enumeration (MCE), which consists to enumerate all maximal complete subgraphs in a given graph, is a fundamental problem in graph theory, and it is used in several applications. It is one of Karp’s 21 NP-complete problems. In the literature, this problem has been widely studied. One of the most notable, efficient, successful and extensively used solutions is the Bron–Kerbosch (BK) algorithm. The latter is a sequential algorithm which is able to enumerate all maximal cliques in an undirected graph without duplication. Furthermore, it is used to solve large problems such as maximum clique problem, community detection and graph clustering. However, for large graphs, sequential algorithms are slow and do not scale well. Thus, processing efficiently this kind of graphs needs to develop distributed algorithms under parallel and distributed platforms or large graph mining frameworks. In this setting, we propose new efficient distributed algorithms for maximal clique enumerating based on the vertex-centric model. These algorithms use the BK algorithm principle to deal with the MCE problem on large cluster. The proposed algorithms are implemented in Giraph and evaluated by using real-world graphs and computer-generated benchmark networks. Our experiments on a Hadoop cluster show that the proposed algorithms can effectively process a variety of large real-world and computer-generated graphs and scale well with increasing the dataset size and the number of nodes in the cluster. Furthermore, the proposed algorithms are provably work-efficient compared with other algorithms including BK algorithm.

Vorheriger Artikel Decentralized iterative approaches for community clustering in the networks

Nächster Artikel A parallel unified transform solver based on domain decomposition for solving linear elliptic PDEs

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

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

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+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

Akkoyunlu EA (1973) The enumeration of maximal cliques of large graphs. SIAM J Comput 2(1):1–6. https://doi.org/10.1137/0202001 MathSciNetMATHCrossRef

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

Bron C, Kerbosch J (1973) Algorithm 457: finding all cliques of an undirected graph. Commun ACM 16(9):575–577. https://doi.org/10.1145/362342.362367 MATHCrossRef

Butenko S, Wilhelm WE (2006) Clique-detection models in computational biochemistry and genomics. Eur J Oper Res 173(1):1–17. https://doi.org/10.1016/j.ejor.2005.05.026 MathSciNetMATHCrossRef

Chen Q, Fang Ch, Wang Z, Suo B, Li Z, Ives ZG (2016) Parallelizing maximal clique enumeration over graph data. In: DASFAA’2016 Proceedings, Part II, of the 21st International Conference on Database Systems for Advanced Applications, vol 9643, pp 249–264. https://doi.org/10.1007/978-3-319-32049-6_16

Cheng J, Zhu L, Ke Y, Chu S (2012) Fast algorithms for maximal clique enumeration with limited memory. In: KDD’12 Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp 1240-1248. https://doi.org/10.1145/2339530.2339724

Chiba N, Nishizeki T (1985) Arboricity and subgraph listing algorithms. SIAM J Comput 14(1):210–223. https://doi.org/10.1137/0214017 MathSciNetMATHCrossRef

Ching A, Edunov S, Kabiljo M, Logothetis D, Muthukrishnan S (2015) One trillion edges: graph processing at facebook-scale. In: Proceedings of the 41st International Conference on Very Large Data Bases, Kohala Coast, Hawaii vol 8(12), pp 1804–1815. https://doi.org/10.14778/2824032.2824077

Conte A, Virgilio RD, Maccioni A, Patrignani M, Torlone R (2016) Finding all maximal cliques in very large social networks. In: Proceedings of the 19th International Conference on Extending Database Technology, EDBT 2016, Bordeaux, France, pp 173–184. https://doi.org/10.5441/002/edbt.2016.18

10.

Dasari NS, Ranjan D, Zubair M (2014) Maximal clique enumeration for large graphs on hadoop framework. In: PPAA’14 Proceedings of the First Workshop on Parallel Programming for Analytics Applications pp 21–30. https://doi.org/10.1145/2567634.2567640

11.

Dasari NS, Zubair M, Ranjan D (2013) A novel parallel algorithm for maximal clique enumeration on multicore and distributed memory architectures. https://pdfs.semanticscholar.org/9827/9e2cedb14085886fcb4473f1ba483a3df195.pdf

12.

Dean J, Ghemawat S (2004) MapReduce: simplified data processing on large clusters. In: OSDI’04, The 6th Symposium on Operating System Design and Implementation, vol 6, California, USA. pp 137–150

13.

Doekemeijer N, Varbanescu AL (2014) A Survey of parallel graph processing frameworks. Technical report, Delft University of Technology, Report number PDS-2014-003

14.

Du N, Bin W, Liutong X, Bai W, Xin P (2006) A parallel algorithm for enumerating all maximal cliques in complex network. In: Proceedings of the Sixth IEEE International Conference on Data Mining—Workshops, Hong Kong, China, pp 320–324. https://doi.org/10.1109/ICDMW.2006.17

15.

Elshawi R, Batarfi O, Fayoumi A, Barnawi A, Sakr S (2015) Big graph processing systems: state-of-the-art and open challenges. In: Big Data Computing Service and Applications (BigDataService), 2015 IEEE First International Conference on Big Data Computing Service and Applications, pp 24–33. https://doi.org/10.1109/BigDataService.2015.11

16.

Elser B, Montresor A (2013) An evaluation study of bigdata frameworks for graph processing. In: 2013 IEEE International Conference on Big Data, pp 60–67. https://doi.org/10.1109/BigData.2013.6691555

17.

Eppstein D, Loffler M, Strash D (2010) Listing all maximal cliques in sparse graphs in near-optimal time. In: Cheong O, Chwa KY, Park K (eds) Algorithms and Computation. ISAAC 2010. Lecture Notes in Computer Science, vol 6506, Springer, Berlin, Heidelberg. pp 403–414. https://doi.org/10.1007/978-3-642-17517-6_36

18.

Fehér P, Asztalos M, Vajk T, Mészàros T, Lengyel L (2017) Detecting subgraph isomorphism with MapReduce. J Supercomput 73(5):1810–1851. https://doi.org/10.1007/s11227-016-1885-6 CrossRef

19.

Giraph A Apache giraph!. https://giraph.apache.org/. Accessed 17 Feb 2018

20.

Golumbic MC (1980) Algorithmic graph theory and perfect graphs. Academic Press, New YorkMATH

21.

Gonzalez JE, Low Y, Gu H, Bickson D, Guestrin C (2012) PowerGraph: distributed graph-parallel computation on natural graphs. In: OSDI’12 Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, CA, USA, pp 17–30

22.

Guo Y, Biczak M, Varbanescu AL, Iosup A, Martella C, Willke TL (2014) How well do graph-processing platforms perform? An empirical performance evaluation and analysis. In: 2014 IEEE 28th International Parallel and Distributed Processing Symposium, pp 395–404. https://doi.org/10.1109/IPDPS.2014.49

23.

Guo Y, Varbanescu AL, Iosup A, Martella C, Willke TL (2014) Benchmarking graph-processing platforms: a vision. In: ICPE’14 Proceedings of the 5th ACM/SPEC International Conference on Performance Engineering, pp 289–292. https://doi.org/10.1145/2568088.2576761

24.

Hadoop A Hadoop. http://hadoop.apache.org. Accessed 17 Feb 2018

25.

Han M, Daudjee K (2015) Giraph unchained: barrierless asynchronous parallel execution in pregel like graph processing systems. In: Proceedings of the VLDB Endowment, vol 8(9), pp 950–961. https://doi.org/10.14778/2777598.2777604

26.

Harary F, Ross IC (1957) A procedure for clique detection using the group matrix. Sociometry 20(3):205–215MathSciNetCrossRef

27.

Harley E, Bonner A, Goodman N (2001) Uniform integration of genome mapping data using intersection graphs. Bioinformatics 17(6):487–494. https://doi.org/10.1093/bioinformatics/17.6.487 CrossRef

28.

Horaud R, Skordas T (1989) Stereo correspondence through feature grouping and maximal cliques. IEEE Trans Pattern Anal Mach Intell 11(11):1168–1180. https://doi.org/10.1109/34.42855 CrossRef

29.

Hou R, Wang C, Zhu Q, Li J (2014) Interference-aware QoS multicast routing for smart grid. Ad Hoc Netw 22:13–26. https://doi.org/10.1016/j.adhoc.2014.05.008 CrossRef

30.

Kaalia R, Srinivasan A, Kumar A, Ghosh I (2016) ILP-assisted de novo drug design. Mach Learn 103(3):309–341. https://doi.org/10.1007/s10994-016-5556-x MathSciNetCrossRef

31.

Kajdanowicz T, Kazienko P, Indyk W (2014) Parallel processing of large graphs. Future Gener Comput Syst 32:324–337. https://doi.org/10.1016/j.future.2013.08.007 CrossRef

32.

Kalavri V, Vlassov V, Haridi S (2018) High-level programming abstractions for distributed graph processing. IEEE Trans Knowl Data Eng 30(2):305–324. https://doi.org/10.1109/TKDE.2017.2762294 CrossRef

33.

Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations. Plenum Press, New York, pp 85–104CrossRef

34.

Koichi S, Arisaka M, Koshino H, Aoki A, Iwata S, Uno T, Satoh H (2014) Chemical structure elucidation from 13C NMR chemical shifts: efficient data processing using bipartite matching and maximal clique algorithms. J Chem Inf Model 54(4):1027–1035. https://doi.org/10.1021/ci400601c CrossRef

35.

Lancichinetti A, Fortunato S, Radicchi F (2008) Benchmark graphs for testing community detection algorithms. Phys Rev E 78(4):046110CrossRef

36.

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

37.

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

38.

Lu L, Gu Y, Grossman R (2010) dMaximalCliques: a distributed algorithm for enumerating all maximal cliques and maximal clique distribution. In: ICDMW’10 Proceedings of the 2010 IEEE International Conference on Data Mining Workshops, pp 1320–1327. https://doi.org/10.1109/ICDMW.2010.13

39.

Low Y, Gonzalez J, Kyrola A, Bickson D, Guestrin C, Hellerstein JM (2012) Dstributed GraphLab: a framework for machine learning and data mining in the Cloud. In: Proceedings of the VLDB Endowment vol 5(8), pp 716–727. https://doi.org/10.14778/2212351.2212354

40.

Malewicz G, Austern MH, Bik AJC, Dehnert JC, Horn I, Leiser N, Czajkowski G (2010) Pregel: a system for large-scale graph processing. In: SIGMOD’10 Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pp 135–146, Indiana, USA. https://doi.org/10.1145/1807167.1807184

41.

Martella C, Shaposhnik R, Logothetis D (2015) Practical graph analytics with apache giraph. Apress, BerkelyCrossRef

42.

Molzahn DK, Holzer JT, Lesieutre BC, DeMarco CL (2013) Implementation of a large-scale optimal power flow solver based on semidefinite programming. IEEE Trans Power Syst 28(4):3987–3998. https://doi.org/10.1109/TPWRS.2013.2258044 CrossRef

43.

Mukherjee AP, Tirthapura S (2014) Enumerating maximal bicliques from a large graph using MapReduce. In: 2014 IEEE International Congress on Big Data, pp 707–716. https://doi.org/10.1109/BigData.Congress.2014.105

44.

Pan L, Santos EE (2008) An anytime-anywhere approach for maximal clique enumeration in social network analysis. In: 2008 IEEE International Conference on Systems, Man and Cybernetics, pp 3529–3535. https://doi.org/10.1109/ICSMC.2008.4811845

45.

Prosser P (2012) Exact algorithms for maximum clique: a computational study. Algorithms 5(4):545–587. https://doi.org/10.3390/a5040545 MathSciNetMATHCrossRef

46.

Sakr S (2013) Processing large-scale graph data: A guide to current technology. IBM Developerworks

47.

Sakr S, Orakzai FM, Abdelaziz I, Khayyat Z (2016) Large-Scale graph processing using Apache Giraph. Springer. https://doi.org/10.1007/978-3-319-47431-1

48.

Salem S, Ozcaglar C (2013) MFMS: Maximal frequent module set mining from multiple human gene expression data sets. In: Proceedings of the 12th International Workshop on Data Mining in Bioinformatics, pp 51–57. https://doi.org/10.1145/2500863.2500869

49.

Schmidt M, Samatova N, Thomas K, Park B (2009) A scalable, parallel algorithm for maximal clique enumeration. J Parallel Distrib Comput 69(4):417–428. https://doi.org/10.1016/j.jpdc.2009.01.003 CrossRef

50.

Shrawak P, Kagzi T, Singh AP, Dobariya B, Lokhande P, Alhat BR (2017) Robotic algorithm development. IJCSIT 8(1):116–119

51.

Spark A (2018) Lightning-fast unified analytics engine. https://spark.apache.org/. Accessed 18 Nov 2018

52.

Svendsen M, Mukherjee AP, Tirthapura S (2015) Mining maximal cliques from a large graph using MapReduce: tackling highly uneven subproblem sizes. J Parallel Distrib Comput 79–80:104–114. https://doi.org/10.1016/j.jpdc.2014.08.011 CrossRef

53.

Tian Y, Balmin A, Corsten SA, Tatikonda S, McPherson J (2013) From “Think Like aVertex” to “Think Like a Graph”. In: Proceedings of the VLDB Endowment, vol 7(3), pp 193–204. https://doi.org/10.14778/2732232.2732238

54.

Tomita E, Akutsu T, Matsunaga T (2011) Efficient algorithms for finding maximum and maximal cliques: effective tools for bioinformatics. Biomed Eng Trends Electron Commun Softw. https://doi.org/10.5772/13245 CrossRef

55.

Tomita E, Tanakaa A, Takahashia H (2006) The worst-case time complexity for generating all maximal cliques and computational experiments. Theor Comput Sci 363(1):28–42. https://doi.org/10.1016/j.tcs.2006.06.015 MathSciNetCrossRef

56.

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

57.

Vlaic S, Conrad T, Tokarski-Schnelle C, Gustafsson M, Dahmen U, Guthke R, Schuster S (2018) ModuleDiscoverer: identification of regulatory modules in protein–protein interaction networks. Sci Rep 8(1):1–11. https://doi.org/10.1038/s41598-017-18370-2 CrossRef

58.

Wu B, Yang S, Zhao H, Wang B (2009) A distributed algorithm to enumerate all maximal cliques in mapreduce. In: Proceedings of the Fourth International Conference on Frontier of Computer Science and Technology, pp 45–51. https://doi.org/10.1109/FCST.2009.30

59.

Xin RS, Crankshaw D, Dave A, Gonzalez JE, Franklin MJ, Stoica I (2014) GraphX: Unifying data-parallel and graph-parallel analytics. In arXiv preprint arXiv:1402.2394

60.

Xin RS, Gonzalez JE, Franklin MJ, Stoica I (2013) GraphX: a resilient distributed graph system on spark. In: GRADES’13 First International Workshop on Graph Data Management Experiences and Systems Article No. 2, New York, USA. https://doi.org/10.1145/2484425.2484427

61.

Xu Y, Cheng J, Fu AW, Bu Y (2014) Distributed maximal clique computation. In: BIGDATACONGRESS’14 Proceedings of the 2014 IEEE International Congress on Big Data, pp 160–167. https://doi.org/10.1109/BigData.Congress.2014.31

62.

Xu Y, Cheng J, Fu AW (2016) Distributed maximal clique computation and management. IEEE Trans Serv Comput 9(1):110–122. https://doi.org/10.1109/TSC.2015.2479225 CrossRef

63.

Yuan P, Zhang W, Xie C, Jin H, Liu L, Lee K (2014) Fast iterative graph computation: a path centric approach. In: SC’14 Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp 401–412. https://doi.org/10.1109/SC.2014.38

64.

Zhang Y, Ren J, Liu J, Xu C, Guo H, Liu Y (2017) A survey on emerging computing paradigms for big data. CJE 26(1):1–12. https://doi.org/10.1049/cje.2016.11.016 CrossRef

Titel: Listing all maximal cliques in large graphs on vertex-centric model
verfasst von: Assia Brighen
Hachem Slimani
Abdelmounaam Rezgui
Hamamache Kheddouci
Publikationsdatum: 12.02.2019
Verlag: Springer US
Erschienen in: The Journal of Supercomputing / Ausgabe 8/2019
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-019-02770-4

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"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 8/2019

Predictive modeling of the performance of asynchronous iterative methods

Safety relay selection algorithms based on fuzzy relationship for wireless sensor networks

An effective security measures for nuclear power plant using big data analysis approach

Enhanced signature RTD transaction scheme based on Chebyshev polynomial for mobile payments service in IoT device environment

Designing a new reversible ALU by QCA for reducing occupation area

Toward fault-tolerant hybrid programming over large-scale heterogeneous clusters via checkpointing/restart optimization