Maximal strongly connected cliques in directed graphs: Algorithms and bounds

Autor: Alessio Conte, Kunihiro Wasa, Takeaki Uno, Mamadou Moustapha Kanté
Přispěvatelé: National Institute of Informatics (NII), Université Clermont Auvergne (UCA), Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA)
Rok vydání: 2021
Předmět:
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
Vertex (graph theory)
Strongly connected component
Network analytics
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
0211 other engineering and technologies
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Bounded delay
Community detection
Directed graphs
Enumeration algorithms
Maximal cliques
Computer Science::Discrete Mathematics
Discrete Mathematics and Combinatorics
Undirected graph
Mathematics
Applied Mathematics
Linear space
021107 urban & regional planning
Directed graph
Enumeration algorithms Bounded delay Directed graphs Community detection Network analytics Maximal cliques
010201 computation theory & mathematics
Exponential space
Polynomial delay
Algorithm
MathematicsofComputing_DISCRETEMATHEMATICS
Network analysis
Zdroj: Discrete Applied Mathematics
Discrete Applied Mathematics, 2021, 303, pp.237-252. ⟨10.1016/j.dam.2020.05.027⟩
ISSN: 0166-218X
DOI: 10.1016/j.dam.2020.05.027
Popis: 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 consider in this paper the problem of listing all maximal strongly connected cliques in a directed graph. We first investigate the combinatorial properties of strongly connected cliques and use them to prove that every n -vertex directed graph has at most 3 n / 3 maximal strongly connected cliques. We then exploit these properties to produce the first algorithms with polynomial delay for enumerating maximal strongly connected cliques: a first algorithm with polynomial delay and exponential space usage, and a second one, based on reverse-search, with higher (still polynomial) delay but which uses linear space. 1
Databáze: OpenAIRE
Externí odkaz: