在数十亿规模上基于传导的有效且高效社区搜索

《IEEE Transactions on Big Data》：Effective and Efficient Conductance-Based Community Search at Billion Scale

社区搜索是半监督图聚类问题，旨在找到包含查询顶点的连接子图。现有方法忽略外部稀疏性，效果不佳。本文提出基于导纳的社区搜索（CCS），设计四阶段算法SCCS：局部采样缩减图集，种子策略获取初始社区，扩展和验证阶段优化。实验验证其在亿级数据集上的有效性、效率及可扩展性。

　　

摘要：

社区搜索是一个被广泛研究的半监督图聚类问题，其目标是找到一个包含用户指定查询顶点的高质量连通子图。然而，现有方法主要关注社区内部的凝聚力，而忽略了社区外部的稀疏性，导致结果不尽如人意。受此启发，我们采用了著名的电导度指标来衡量社区的质量，并提出了一种基于电导度的社区搜索（CCS）新方法。CCS的目标是在所有包含查询顶点的连通子图中找到电导度最小的子图。我们证明了CCS问题属于NP难问题。为了高效地解决CCS问题，我们提出了一种四阶段的基于子图电导度的社区搜索算法SCCS。具体来说，首先利用局部采样技术大幅简化整个图；然后采用三阶段的局部优化策略不断改进社区质量：首先通过种子策略获得一个初始社区以增强其内部凝聚力；接着在扩展阶段迭代添加符合条件的顶点，以确保社区的内部凝聚力和外部稀疏性；最后在验证阶段逐步移除不合格的顶点。在包含十亿级图的真实世界数据集和合成数据集上的广泛实验表明，我们的解决方案具有有效性、高效性和可扩展性。

引言

社区搜索是指在网络科学[2]、[7]、[13]、[14]、[20]中识别出一个包含给定查询顶点的高质量连通子图（称为社区）的基本任务。该问题在许多实际应用中也具有重要意义，包括社交推荐[2]、蛋白质复合物识别[7]以及即兴活动的组织[20]。因此，文献中提出了许多社区搜索模型，其中著名的例子包括基于-核的模型[2]、[7]、[21]，以及基于-骨架的模型[22]、[23]。