不确定图中的极大团高效挖掘算法

摘要

为了提高不确定图中极大团挖掘的效率,针对经典极大团挖掘算法中递归次数多与顶点集合更新耗时的问题,结合团概率的定义,提出了递归前计算集合概率来减少递归次数的不确定图中极大团挖掘算法.在已有算法的基础上只维持候选顶点集合,删除已使用顶点集合的计算,根据候选顶点集合和待扩展顶点集合的大小,从两种情况计算扩展后的集合概率,验证是否为α-团.对于挖掘到的全部α-团,提出了改进的极大团验证算法,结合伪极大团首先被顶点数量最多的极大团包含的特性,利用顶点的倒排表去除伪极大团.通过在不同的真实数据集上进行实验测试,验证了改进后的算法具有更高的执行效率.