-
题名满足强连通性的有向团枚举算法研究
- 1
-
-
作者
陈久健
代强强
李荣华
王国仁
-
机构
北京理工大学计算机学院
-
出处
《计算机科学与探索》
CSCD
北大核心
2024年第5期1211-1222,共12页
-
基金
国家重点研发计划(2021YFB3301301)。
-
文摘
有向图的有向边可以表示关系的指向或者数据的传递,在稠密子图的挖掘中引入连通性的约束可以增加顶点之间的联系。为此,结合极大团与强连通分量的定义,底图是完全子图且顶点之间满足强连通性的子图结构被称为有向团。已有工作给出了枚举极大有向团的输出敏感算法,然而其存在大量重复枚举和判重操作复杂等不足之处。为了解决这些问题,基于深度优先搜索的思想和有向团的扩展性质,提出一种新颖的递归枚举算法。算法对于出边邻居和入边邻居分别划分候选集与排除集,维护完全子图结构的同时,不断尝试扩展有向团并保证满足强连通性,并且引入基于共同邻居的支撑点剪枝策略,在稠密图上获得上千倍的效率优化。算法还针对搜索空间给出两种优化设计:一是添加了分割子图的预处理,限制递归调用的搜索范围;二是基于位向量压缩表示顶点集合,提高集合运算的效率。在真实图数据上的实验结果表明,相比现有工作中的输出敏感算法,提出的算法具有50倍以上的加速比。
-
关键词
图数据挖掘
有向团
强连通性
支撑点剪枝
位向量压缩
-
Keywords
graph data mining
directed clique
strongly connected
pivot pruning
bitwise compression
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
