何瀛龙 王梦博 白雨 李源

（北方工业大学信息学院 北京市 100144）

1 引言

在大规模的网络分析中，分量检测是非常重要的问题之一。发现高度连通的分量可以帮助我们解决许多现实生活中的实际问题，例如，社会网络群体的结构凝聚力是研究社会群体凝聚力的重要的社会学指标；从城市网络中发现了凝聚子群进而研究影响因素以及措施；在信息传播中能描述出网络核心位置，有助于发现信息传播中的关键节点。

本文主要研究k-点连通分量（k-VCC），k-VCC 和社会学中的结构凝聚力概念是等价的，除此之外k-VCC 还有许多重要的特征。首先根据惠特尼定理，k-VCC 被包含在k-核（k-core）和k-边连通分量（k-ECC）之中，因此k-VCC拥有着k-core 和k-ECC 的所有结构特性，更具有凝聚力。k-VCC 允许分量之间允许重叠，在真实复杂网络中分量重叠也是重要且自然的特征。

给定图G 和一个整数k，如何计算出G 的所有k-VCCs。现有算法一般思路是，将图G 递归地划分为重叠的子图。若G 不是k-VCC，则找到一组小于k 的点割集对G 进行划分。这种自顶向下的框架的关键在于最小点割集的计算，可以转化为对局部连通度的测试，也就是判断两个顶点u,v 是否能从G 中移除最多k-1 个点使得u,v 之间不连通。局部连通度的测试利用网络流算法可以实现。而为了找到图中一组小于k 的点割集，在最坏情况下将对图G 的每对顶点都进行局部连通度的测试，若在规模较大的图中，这样做在时间上的开销是高昂的。Dong等人提出了一种减少局部连通度测试次数的优化。……