Maximal η-clique maintenance over uncertain graph streams

Maximal clique enumeration is a critical task for analyzing graph data and has a wide range of applications, such as community detection, protein complex identification, and group recommendation. Although many efficient algorithms have been proposed, most of them are designed for static or deterministic graphs. However, in many real-life applications, graphs are often highly dynamic and nondeterministic. In this paper, we study the problem of maximal η-clique maintenance (shorted as MCM) over uncertain graph streams. Given an uncertain graph G and a probability threshold η, MCM reports all incremental η-cliques in G for each update edge of G. To the best of our knowledge, we are the first to systematically study this problem. We first develop a local pivot-based enumeration technique that utilizes the pivot priority of candidates to achieve effective pruning during the maximal η-clique enumeration procedure. Based on the technique, we propose a competitive baseline approach LPMCM, which finds newly generated maximal η-cliques and internal maximal η-cliques. Although LPMCM avoids repeated enumeration of the same maximal η-cliques, it still requires expensive costs in terms of η-clique maximality determination. To further enhance maintenance efficiency, we introduce an approach HLPMCM using the hash-based maximality determination technique and an improved internal maximal η-clique enumeration technique. Extensive experiments show that HLPMCM can achieve 1.1x-19.0x speedup over the competitors and consumes slightly more memory.