Research on Directed Clique Enumeration with Strongly Connected Constraint

Abstract

Directed edges in a directed graph can represent the direction of relationships or the transmission of data. Introducing connectivity constraints in the mining of dense subgraphs can enhance the connections between vertices. Accordingly, by combining the definitions of maximal cliques and strongly connected components, a directed clique is a subgraph structure where the underlying graph is a complete subgraph and the vertices are strongly connected. Existing work has proposed an output-sensitive algorithm for enumerating maximal directed cliques, but it suffers from lots of repeated enumerations and complex deduplication operations. To address these issues, a novel recursive enumeration algorithm based on depth-first search and the characteristics of directed clique extension is proposed. The algorithm divides the outgoing and incoming neighbors into candidate and excluded sets respectively. While preserving the structure of complete subgraph, it constantly tries to extend the directed cliques and ensures that they are strongly connected. Additionally, the algorithm adopts a pivot pruning strategy based on common neighbors, achieving efficiency optimization of over a thousand times on dense graphs. Furthermore, the algorithm utilizes two optimization designs for the search space: firstly, a pre-processing step is introduced to divide subgraphs and narrow the search for the recursion; secondly, a bitwise compression representation is proposed for vertex sets to improve the efficiency of set operations. Experimental results on real-world graphs demonstrate that the proposed algorithm achieves a speedup of more than 50x compared with the existing output-sensitive algorithm.

Keywords

• graph data mining; directed clique; strongly connected; pivot pruning; bitwise compression