License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.23
URN: urn:nbn:de:0030-drops-82284
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8228/
Go to the corresponding LIPIcs Volume Portal

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

On Maximal Cliques with Connectivity Constraints in Directed Graphs

pdf-format:
LIPIcs-ISAAC-2017-23.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{conte_et_al:LIPIcs:2017:8228,
  author =	{Alessio Conte and Mamadou Moustapha Kant{\'e} and Takeaki Uno and Kunihiro Wasa},
  title =	{{On Maximal Cliques with Connectivity Constraints in Directed Graphs}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{23:1--23:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Yoshio Okamoto and Takeshi Tokuyama},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8228},
  URN =		{urn:nbn:de:0030-drops-82284},
  doi =		{10.4230/LIPIcs.ISAAC.2017.23},
  annote =	{Keywords: Enumeration algorithms, Bounded delay, Directed graphs, Community structure, Network analytics}
}

Keywords: Enumeration algorithms, Bounded delay, Directed graphs, Community structure, Network analytics
Collection: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue Date: 2017
Date of publication: 07.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI