Incremental maximal clique enumeration (IMCE), which maintains maximal cliques in dynamic graphs, is a fundamental problem in graph analysis. A maximal clique has a solid descriptive power of dense structures in graphs. Real-world graph data is often large and dynamic. Studies on IMCE face significant challenges in the efficiency of incremental batch computation and hybrid edge changes. Moreover, with growing graph sizes, new requirements occur on indexing global maximal cliques and obtaining maximal cliques under specific vertex scope constraints. This work presents a new data structure SOMEi to maintain intermediate maximal cliques during construction. SOMEi serves as a space-efficient index to retrieve scope-constrained maximal cliques on the fly. Based on SOMEi, we design a procedure-oriented IMCE algorithm to deal with hybrid edge changes within a unified algorithm framework. In particular, the algorithm is able to process a large batch of edge changes and significantly improve the average processing time of a single edge change through an efficient pruning strategy. Experimental results on real and synthetic graph data demonstrate that the proposed algorithm outperforms all the baselines and achieves good efficiency through pruning.

Streaming computation for large graphs on parallel systems faces challenges in task decomposition, data skew, and resource scheduling. In this work, we propose a general parallel streaming framework for the node-centered graph algorithms to improve the computation efficiency. We construct the parallel procedure of the incremental maximal clique enumeration (IMCE) task and accelerate the incremental Candidate Map Constructor (CMC) algorithm through the framework for large-scale streaming graphs. Experimental results on three large real-world graphs show the framework’s positive effect on the algorithm’s execution time.