一种面向不确定极大团枚举的高效验证算法

摘要

极大团作为稠密子图中具有代表性的一种,一直是数据挖掘领域关注的重点。极大团中蕴含的重要数据信息也被广泛应用于各种领域,例如社交网络中的社区发现等。本文研究在不确定图上枚举所有极大团的问题。现有方法基于"子图划分-求解-验证"的思想,可以有效利用极大团性质加速计算过程,但其问题在于验证算法DPMC的效率不稳定。当满足条件的极大团数量增多时,验证的效率会急速下降,严重影响系统的整体性能。本文提出一种高效的验证算法FDPMU,通过构建映射表以及动态构建的倒排表,提高了算法的运行效率。最后,在多个真实数据集上进行比较,实验结果验证了FDPMU算法的高效性。