Sublinear-Space Bounded-Delay Enumeration for Massive Network Analytics: Maximal Cliques * - Archive ouverte HAL Access content directly
Conference Papers Year : 2016

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

(1) , (1, 2) , (1) , (1)
1
2

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.
Fichier principal
Vignette du fichier
LIPIcs-ICALP-2016-148.pdf (632.59 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01388461 , version 1 (27-10-2016)

Identifiers

Cite

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. pp.1 - 148, ⟨10.4230/LIPIcs.ICALP.2016.148⟩. ⟨hal-01388461⟩

Collections

INRIA INRIA2
195 View
248 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More