应用子图划分策略的不确定图极大团枚举算法

为了更加高效地枚举出不确定图极大团,通过对现有确定图和不确定图极大团枚举算法进行研究,结合在相同图结构下确定图极大团与不确定图极大团之间的关系,提出了一种基于相同图结构确定图极大团子图划分的高效不确定图极大团枚举算法D-MULE-D。通过在不同的真实数据集上进行实验测试,对比D-MULE-D算法和MULE算法的运行时间,验证D-MULE-D算法的可行性和高效性。

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

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