计算机科学与探索

作者：陈久健, 代强强, 李荣华, 王国仁

单位：北京理工大学 计算机学院，北京 100081

关键词：图数据挖掘,有向团,强连通性,支撑点剪枝,位向量压缩

有向图的有向边可以表示关系的指向或者数据的传递，在稠密子图的挖掘中引入连通性的约束可以增加顶点之间的联系。为此，结合极大团与强连通分量的定义，底图是完全子图且顶点之间满足强连通性的子图结构被称为有向团。已有工作给出了枚举极大有向团的输出敏感算法，然而其存在大量重复枚举和判重操作复杂等不足之处。为了解决这些问题，基于深度优先搜索的思想和有向团的扩展性质，提出一种新颖的递归枚举算法。算法对于出边邻居和入边邻居分别划分候选集与排除集，维护完全子图结构的同时，不断尝试扩展有向团并保证满足强连通性，并且引入基于共同邻居的支撑点剪枝策略，在稠密图上获得上千倍的效率优化。算法还针对搜索空间给出两种优化设计：一是添加了分割子图的预处理，限制递归调用的搜索范围；二是基于位向量压缩表示顶点集合，提高集合运算的效率。在真实图数据上的实验结果表明，相比现有工作中的输出敏感算法，提出的算法具有50倍以上的加速比。

来源：2024年第5期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2024年第5期