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

【Abstract】 The classic algorithm for mining maximal cliques in uncertain graphs has many recursions, and it takes time to update the vertex set.In this paper, an algorithm based on the definition of clique probability is proposed, which improves the efficiency of maximal clique mining in uncertain graphs.To reduce the number of recursions, the set probability will be calculated before recursion.On the basis of the existing algorithm, only the candidate vertex set is maintained, and the calculation of the used vertex set is deleted.According to the size of the candidate vertex set and the set of vertices to be expanded, the probability of the expanded set is calculated from two cases to verify whether it is α-clique.For all α-cliques obtained by the algorithm, an improved algorithm for maximal clique verification is proposed.Pseudo-maximal cliques are first included by the maximal clique with the largest number of vertices.Combining this characteristic, the pseudo-maximal cliques can be removed through the inverted list of vertices.Experiments on different real datasets show that the improved algorithm has higher efficiency.更多还原