Document Open Access Logo

Sublinear-Space Bounded-Delay Enumeration for Massive Network Analytics: Maximal Cliques

Authors Alessio Conte, Roberto Grossi, Andrea Marino, Luca Versari

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.148.pdf
  • Filesize: 0.61 MB
  • 15 pages

Document Identifiers

Author Details

Alessio Conte
Roberto Grossi
Andrea Marino
Luca Versari

Cite As Get BibTex

Alessio Conte, Roberto Grossi, Andrea Marino, and Luca Versari. Sublinear-Space Bounded-Delay Enumeration for Massive Network Analytics: Maximal Cliques. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 148:1-148:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.148

Abstract

Due to the sheer size of real-world networks, delay and space become quite relevant measures for the cost of enumeration in network analytics. This paper presents efficient algorithms for listing maximum cliques in networks, providing the first sublinear-space bounds with guaranteed delay per enumerated clique, thus comparing favorably with the known literature.

Subject Classification

Keywords
  • Enumeration algorithms
  • maximal cliques
  • network mining and analytics
  • reverse search
  • space efficiency

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Nesreen K. Ahmed, Jennifer Neville, Ryan A. Rossi, and Nick G. Duffield. Efficient graphlet counting for large networks. In 2015 IEEE International Conference on Data Mining, ICDM 2015, pages 1-10. IEEE, 2015. Google Scholar
  2. E. A. Akkoyunlu. The enumeration of maximal cliques of large graphs. SIAM J. Comput., 2(1):1-6, 1973. Google Scholar
  3. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. Google Scholar
  4. David Avis and Komei Fukuda. Reverse search for enumeration. Discrete Applied Mathematics, 65(1-3):21-46, 1996. Google Scholar
  5. Edward Bierstone. Cliques and generalized cliques in a finite linear graph. Unpublished report, 1960. Google Scholar
  6. Andreas Björklund, Rasmus Pagh, Virginia Vassilevska Williams, and Uri Zwick. Listing triangles. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings, Part I, pages 223-234, 2014. Google Scholar
  7. Coenraad Bron and Joep Kerbosch. Finding all cliques of an undirected graph (algorithm 457). Commun. ACM, 16(9):575-576, 1973. Google Scholar
  8. Frédéric Cazals and Chinmay Karande. A note on the problem of reporting maximal cliques. Theor. Comput. Sci., 407(1-3):564-568, 2008. Google Scholar
  9. Lijun Chang, Jeffrey Xu Yu, and Lu Qin. Fast maximal cliques enumeration in sparse graphs. Algorithmica, 66(1):173-186, 2013. Google Scholar
  10. James Cheng, Linhong Zhu, Yiping Ke, and Shumo Chu. Fast algorithms for maximal clique enumeration with limited memory. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD, pages 1240-1248, 2012. Google Scholar
  11. Norishige Chiba and Takao Nishizeki. Arboricity and subgraph listing algorithms. SIAM Journal on Computing, 14(1):210-223, 1985. Google Scholar
  12. Carlo Comin and Romeo Rizzi. An improved upper bound on maximal clique listing via rectangular fast matrix multiplication. CoRR, abs/1506.01082, 2015. URL: http://arxiv.org/abs/1506.01082.
  13. Alessio Conte, Roberto De Virgilio, Antonio Maccioni, Maurizio Patrignani, and Riccardo Torlone. Finding all maximal cliques in very large social networks. In Proceedings of the 19th International Conference on Extending Database Technology, EDBT 2016., pages 173-184, 2016. Google Scholar
  14. Nan Du, Bin Wu, Liutong Xu, Bai Wang, and Pei Xin. Parallel algorithm for enumerating maximal cliques in complex network. In Mining Complex Data, pages 207-221. Springer, 2009. Google Scholar
  15. David Eppstein, Maarten Löffler, and Darren Strash. Listing all maximal cliques in sparse graphs in near-optimal time. In ISAAC (1), pages 403-414, 2010. Google Scholar
  16. David Eppstein, Maarten Löffler, and Darren Strash. Listing all maximal cliques in large sparse real-world graphs. ACM Journal of Experimental Algorithmics, 18, 2013. Google Scholar
  17. Komei Fukuda. Note on new complexity classes ENP, EP and CEP. https://www.inf.ethz.ch/personal/fukudak/old/ENP_home/ENP_note.html, 1996. Accessed: 2016-02-17.
  18. Leonhard Gerhards and Wolfgang Lindenberg. Clique detection for nondirected graphs: Two new algorithms. Computing, 21(4):295-322, 1979. Google Scholar
  19. Eo N. Gilbert. Enumeration of labelled graphs. Canad. J. Math, 8(1):05-411, 1956. Google Scholar
  20. Alain Gély, Lhouari Nourine, and Bachir Sadi. Enumeration aspects of maximal cliques and bicliques. Discrete Applied Mathematics, 157(7):1447-1459, 2009. Google Scholar
  21. Christopher J. Henry and Sheela Ramanna. Transactions on Rough Sets XVI, chapter Maximal Clique Enumeration in Finding Near Neighbourhoods, pages 103-124. Springer, 2013. Google Scholar
  22. Alon Itai and Michael Rodeh. Finding a minimum circuit in a graph. SIAM J. Comput., 7(4):413-423, 1978. Google Scholar
  23. David S. Johnson, Mihalis Yannakakis, and Christos H. Papadimitriou. On generating all maximal independent sets. Information Processing Letters, 27(3):119-123, 1988. URL: http://dx.doi.org/10.1016/0020-0190(88)90065-8.
  24. H. C. Johnston. Cliques of a graph-variations on the Bron-Kerbosch algorithm. International Journal of Parallel Programming, 5(3):209-238, 1976. Google Scholar
  25. Kazuhisa Makino and Takeaki Uno. New algorithms for enumerating all maximal cliques. In Algorithm Theory-SWAT 2004, pages 260-272. Springer, 2004. Google Scholar
  26. R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network motifs: simple building blocks of complex networks. Science, 298:824-827, 2002. Google Scholar
  27. John W. Moon and Leo Moser. On cliques in graphs. Israel journal of Mathematics, 3(1):23-28, 1965. Google Scholar
  28. Gordon D. Mulligan and Derek G. Corneil. Corrections to Bierstone’s algorithm for generating cliques. J. ACM, 19(2):244-247, 1972. Google Scholar
  29. Long Pan and Eunice E. Santos. An anytime-anywhere approach for maximal clique enumeration in social network analysis. In SMC, pages 3529-3535. IEEE, 2008. Google Scholar
  30. Frank Ruskey. Combinatorial Generation. 2003. Google Scholar
  31. Thomas Schank and Dorothea Wagner. Finding, counting and listing all triangles in large graphs, an experimental study. In Experimental and Efficient Algorithms, 4th InternationalWorkshop, WEA 2005, Proceedings, pages 606-609, 2005. Google Scholar
  32. Matthew C. Schmidt, Nagiza F. Samatova, Kevin Thomas, and Byung-Hoon Park. A scalable, parallel algorithm for maximal clique enumeration. Journal of Parallel and Distributed Computing, 69(4):417-428, 2009. Google Scholar
  33. Nino Shervashidze, S V N Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten M. Borgwardt. Efficient graphlet kernels for large graph comparison. In Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, AISTATS 2009, volume 5 of JMLR Proceedings, pages 488-495, 2009. Google Scholar
  34. Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments. Theor. Comput. Sci., 363(1):28-42, 2006. Google Scholar
  35. Horace M. Trent. A note on the enumeration and listing of all possible trees in a connected linear graph. Proceedings of the National Academy of Sciences, 40(10):1004-1007, 1954. Google Scholar
  36. Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa. A new algorithm for generating all the maximal independent sets. SIAM J. Comput., 6(3):505-517, 1977. Google Scholar
  37. Takeaki Uno. Two general methods to reduce delay and change of enumeration algorithms. National Institute of Informatics (in Japan) Technical Report E, 4:2003, 2003. Google Scholar
  38. Takeaki Uno. An efficient algorithm for solving pseudo clique enumeration problem. Algorithmica, 56(1):3-16, 2008. Google Scholar
  39. Leslie G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8(2):189-201, 1979. Google Scholar
  40. Kunihiro Wasa, Hiroki Arimura, and Takeaki Uno. Efficient enumeration of induced subtrees in a k-degenerate graph. In Hee-Kap Ahn and Chan-Su Shin, editors, Algorithms and Computation: 25th International Symposium, ISAAC 2014, Proceedings, pages 94-102, Cham, 2014. Springer International Publishing. Google Scholar
  41. Yanyan Xu, James Cheng, Ada Wai-Chee Fu, and Yingyi Bu. Distributed maximal clique computation. In Big Data (BigData Congress), 2014 IEEE International Congress on, pages 160-167. IEEE, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact