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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [40 references]  Display  Hide  Download
Contributor : Marie-France Sagot <>
Submitted on : Thursday, October 27, 2016 - 9:55:01 AM
Last modification on : Tuesday, February 26, 2019 - 10:54:02 AM


Files produced by the author(s)




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⟩



Record views


Files downloads