扩展k-团渗透社区检测算法

《Proceedings of the ACM on Management of Data》：Scaling Up k-Clique Percolation Community Detection

针对现有k-团渗透社区挖掘方法效率低、扩展性差的问题，本文提出基于最大团枚举和k-团列表的优化算法。通过引入准k-团渗透社区（Quasi-KCPC）概念，显著缩减最大团邻接图规模，并结合k-团列表的动态连接策略，提升挖掘效率达两个数量级。同时设计动态更新算法以支持实时分析，实验验证其在12个大规模真实图上的优越性。

　　

摘要

在现实世界的网络中，重叠社区非常普遍，节点通常会同时参与多个社区。k-团渗透社区（KCPC）模型是挖掘重叠社区的基本范式。然而，现有的KCPC挖掘方法往往受到效率低下和可扩展性挑战的制约，这限制了它们在大型网络中的应用。为了解决这些问题，我们从最大团和k-团的角度提出了几种新颖且高效的方法来挖掘KCPC。具体来说，我们首先提出了一种称为“准KCPC”的新概念，它代表了一个不完整的KCPC，并且可以在最大团枚举过程中作为副产品高效获得。基于准KCPC，我们首先提出了一种基于最大团枚举的解决方案，该方案在现有最大团邻接图遍历方法的基础上进行了改进，通过使用准KCPC大幅减少了最大团邻接图的规模，从而提高了效率。此外，我们还提出了一种基于k-团列表的解决方案，该方法采用了不同的策略：它首先枚举(k-1)团，然后将共享这些(k-1)团的k-团连接成KCPC。我们的方法通过将连接目标从k-团转移到最大团，并利用准KCPC显著修剪k-团枚举树，进一步提高了效率。我们还提出了KCPC的更新算法，以处理节点和边的动态添加和删除，从而实现KCPC的实时分析。在12个大型真实世界图上的广泛实验表明，我们的算法具有优越性，其速度比现有的最先进KCPC挖掘方法快两个数量级，比动态KCPC更新中的重新计算策略快近两个数量级。