Document Open Access Logo

On Maximal Cliques with Connectivity Constraints in Directed Graphs

Authors Alessio Conte, Mamadou Moustapha Kanté, Takeaki Uno, Kunihiro Wasa

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.23.pdf
  • Filesize: 0.54 MB
  • 13 pages

Document Identifiers

Author Details

Alessio Conte
Mamadou Moustapha Kanté
Takeaki Uno
Kunihiro Wasa

Cite As Get BibTex

Alessio Conte, Mamadou Moustapha Kanté, Takeaki Uno, and Kunihiro Wasa. On Maximal Cliques with Connectivity Constraints in Directed Graphs. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.23

Abstract

Finding communities in the form of cohesive subgraphs is a fundamental problem in network analysis. In domains that model networks as undirected graphs, communities are generally associated with dense subgraphs, and many community models have been proposed. 
Maximal cliques are arguably the most widely studied among such models, with early works dating back to the '60s, and a continuous stream of research up to the present. In domains that model networks as directed graphs, several approaches for community detection have been proposed, but there seems to be no clear model of cohesive subgraph, i.e., of what a community should look like. We extend the fundamental model of clique to directed graphs, adding the natural constraint of strong connectivity within the clique. We characterize the problem by giving a tight bound for the number of such cliques in a graph, and highlighting useful structural properties. We then exploit these properties to produce the first algorithm with polynomial delay for enumerating maximal strongly connected cliques.

Subject Classification

Keywords
  • Enumeration algorithms
  • Bounded delay
  • Directed graphs
  • Community structure
  • Network analytics

Metrics

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

References

  1. Eralp Abdurrahim Akkoyunlu. The enumeration of maximal cliques of large graphs. SIAM J Comput, 2(1):1-6, 1973. Google Scholar
  2. Hiroki Arimura and Takeaki Uno. Polynomial-delay and polynomial-space algorithms for mining closed sequences, graphs, and pictures in accessible set systems. In Proceedings of the 2009 SIAM International Conference on Data Mining, pages 1088-1099. SIAM, 2009. Google Scholar
  3. Baruch Awerbuch and Yuval Shavitt. Topology aggregation for directed graphs. IEEE/ACM Transactions On Networking, 9(1):82-90, 2001. Google Scholar
  4. Devora Berlowitz, Sara Cohen, and Benny Kimelfeld. Efficient enumeration of maximal k-plexes. In SIGMOD, pages 431-444, New York, NY, USA, 2015. ACM. Google Scholar
  5. Coenraad Bron and Joep Kerbosch. Finding all cliques of an undirected graph (algorithm 457). Commun. ACM, 16(9):575-576, 1973. Google Scholar
  6. Moses Charikar. Greedy approximation algorithms for finding dense components in a graph. In APPROX, pages 84-95. Springer, 2000. Google Scholar
  7. Sara Cohen, Benny Kimelfeld, and Yehoshua Sagiv. Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties. Journal of Computer and System Sciences, 74(7):1147 - 1159, 2008. Google Scholar
  8. Carlo Comin and Romeo Rizzi. An improved upper bound on maximal clique listing via rectangular fast matrix multiplication. CoRR, abs/1506.01082, 2015. Google Scholar
  9. Alessio Conte, Roberto Grossi, Andrea Marino, Romeo Rizzi, and Luca Versari. Directing road networks by listing strong orientations. IWOCA, pages 83-95, 2016. Google Scholar
  10. Alessio Conte, Roberto Grossi, Andrea Marino, and Luca Versari. Sublinear-space bounded-delay enumeration for massive network analytics: Maximal cliques. In ICALP, 2016. Google Scholar
  11. Reinhard Diestel. Graph Theory (Graduate Texts in Mathematics). Springer, 2005. Google Scholar
  12. 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
  13. Santo Fortunato. Community detection in graphs. Physics reports, 486(3):75-174, 2010. Google Scholar
  14. Komei Fukuda. Note on new complexity classes ENP, EP and CEP, 1996. Accessed: 02-2016. URL: https://www.inf.ethz.ch/personal/fukudak/old/ENP_home/ENP_note.html.
  15. Gaurav Goel and Jens Gustedt. Bounded arboricity to determine the local structure of sparse graphs. In WG, pages 159-167. Springer, 2006. Google Scholar
  16. Björn H. Junker and Falk Schreiber. Analysis of biological networks, volume 2. John Wiley &Sons, 2011. Google Scholar
  17. Jon M. Kleinberg, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew S. Tomkins. The web as a graph: Measurements, models, and methods. In International Computing and Combinatorics Conference, pages 1-17. Springer, 1999. Google Scholar
  18. Darong Lai, Hongtao Lu, and Christine Nardini. Finding communities in directed networks by pagerank random walk induced network embedding. Physica A: Statistical Mechanics and its Applications, 389(12):2443-2454, 2010. Google Scholar
  19. Elizabeth A. Leicht and Mark E.J. Newman. Community structure in directed networks. Physical review letters, 100(11):118703, 2008. Google Scholar
  20. Kazuhisa Makino and Takeaki Uno. New algorithms for enumerating all maximal cliques. In Algorithm Theory-SWAT 2004, pages 260-272. Springer, 2004. Google Scholar
  21. John W. Moon and Leo Moser. On cliques in graphs. Isr J Math, 3(1):23-28, 1965. Google Scholar
  22. Jeffrey Pattillo, Nataly Youssef, and Sergiy Butenko. Clique relaxation models in social network analysis. Handbook of Optimization in Complex Networks, pages 143-162, 2012. Google Scholar
  23. Martin Rosvall and Carl T. Bergstrom. Maps of random walks on complex networks reveal community structure. P Natl Acad Sci USA, 105(4):1118-1123, 2008. Google Scholar
  24. Matthew C. Schmidt, Nagiza F. Samatova, Kevin Thomas, and Byung-Hoon Park. A scalable, parallel algorithm for maximal clique enumeration. J Parallel Distr Com, 69(4):417-428, 2009. Google Scholar
  25. John Scott. Social network analysis. Sage, 2012. Google Scholar
  26. 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
  27. Takeaki Uno. Two general methods to reduce delay and change of enumeration algorithms. NII Technical Report NII-2003-004E, Tokyo, Japan, 4, 2003. Google Scholar
  28. Stanley Wasserman and Katherine Faust. Social network analysis: Methods and applications, volume 8. Cambridge university press, 1994. 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