计算机科学与探索2024，Vol.18Issue(5)：1211-1222,12.DOI:10.3778/j.issn.1673-9418.2303079
满足强连通性的有向团枚举算法研究
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.关键词
图数据挖掘/有向团/强连通性/支撑点剪枝/位向量压缩Key words
graph data mining/directed clique/strongly connected/pivot pruning/bitwise compression分类
信息技术与安全科学引用本文复制引用
陈久健,代强强,李荣华,王国仁..满足强连通性的有向团枚举算法研究[J].计算机科学与探索,2024,18(5):1211-1222,12.基金项目
国家重点研发计划(2021YFB3301301). This work was supported by the National Key Research and Development Program of China(2021YFB3301301). （2021YFB3301301）
