极大团是稠密子图的一种,极大团枚举用于从给定图中挖掘不被其他团包含的完全子图,其中Top-K极大团枚举用于返回规模最大的K个极大团,在生物医疗、社交网络等应用中找到关系密切的顶点集合用于辅助分析。相较于确定图,实际应用中的数据图往往带有概率信息,用以刻画数据不完整或不精确的程度或者可能性。现有方法在概率图上求解Top-K极大团时,返回的是概率最大的前K个极大团。由于极大团的概率会随着顶点规模的变大而不断减小,这种方式会丢掉顶点规模大而概率较小的极大团,而这些被丢掉的极大团规模较大,在实际中具有重要的应用价值。本文研究概率图上的Top-K极大团枚举问题,具体研究内容如下。首先,本文重新定义了概率图上的Top-K极大团枚举问题,用于返回概率值大于给定阈值的前K个规模最大的极大团。在此基础上,提出了一种在概率图上枚举Top-K极大团的基础算法Top-KC。该算法通过维护一个大小为K的结果集来保存当前的Top-K极大团,并在枚举极大团的过程中不断对其进行更新,保证结果集中团的顶点规模尽可能大。针对基础算法存在的冗余计算问题,本文提出了两种优化策略来加快Top-KC算法枚举极大团的速度。分别是基于顶点的度和核心值进行排序和剪枝,以此来减少需要枚举的极大团数量,避免不必要的计算。其次,提出了基于边的三角形数量的预处理策略来化简数据图的规模,从而减小极大团枚举算法的计算代价。其基本思想是在枚举之前计算每条边能被多少个三角形包含,如果数量小于2,则说明该边对应的两个顶点能参与的最大团规模是三个顶点,因此可以将该边删除,以减小图的规模。基于这种策略对图进行简化之后,再应用以上两种优化策略,可显著提升Top-K极大团的求解效率。最后,基于15个真实数据集进行了实验,以Top-K极大团求解过程中所枚举极大团的数量和计算总时间为指标,对本文提出的算法的高效性进行了验证。实验结果证明,基于度的优化策略和基于核心值的优化策略能够有效提高枚举极大团的效率,基于边的三角形数量的删边策略能在前两种优化的基础上进一步减少计算时间。