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

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. 1998 ACM Subject Classification E. 1 Introduction The design of efficient algorithms for enumerating all possible solutions of a given problem dates back to the 1950s [5, 19, 35]. Enumeration algorithms have the purpose of either counting the number of solutions or listing the solutions one by one. Their study originated in the area of complexity and optimization [17, 23, 39], and then spread over several other application domains, including bioinformatics, machine learning, network analytics, and social analysis [1, 26, 33]. For instance, a number of papers described how to enumerate triangles [6, 3, 22, 31] and their generalizations such as cliques or other dense subgraphs [7, 9, 11, 12, 14, 15, 21, 25, 29, 34, 38]. Among the first problems attacked is the enumeration of maximal cliques [2, 5, 7, 18, 24, 28], where a maximal clique is a subset of pairwise connected vertices that is maximal under inclusion. This paper focuses on two worst-case efficiency measures, namely, delay and space, that become relevant for enumeration in massive networks. The delay is the maximum latency between any two consecutively reported solutions. The space is the maximum amount of extra memory that should be allocated to enumerate all the solutions, besides the amount required by the input graph.
Type de document :
Communication dans un congrès
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Jul 2016, Schloss Dagstuhl, Germany. 148, pp.1 - 148, 2016, 〈10.4230/LIPIcs.ICALP.2016.148〉
Liste complète des métadonnées

Littérature citée [40 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01388461
Contributeur : Marie-France Sagot <>
Soumis le : jeudi 27 octobre 2016 - 09:55:01
Dernière modification le : mercredi 11 avril 2018 - 01:56:15

Fichier

LIPIcs-ICALP-2016-148.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Alessio Conte, Roberto Grossi, Andrea Marino, Luca Versari. Sublinear-Space Bounded-Delay Enumeration for Massive Network Analytics: Maximal Cliques *. 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Jul 2016, Schloss Dagstuhl, Germany. 148, pp.1 - 148, 2016, 〈10.4230/LIPIcs.ICALP.2016.148〉. 〈hal-01388461〉

Partager

Métriques

Consultations de la notice

189

Téléchargements de fichiers

184