大规模网络中k-点连通分量发现算法研究

摘要

本文研究给定一个图G和一个整数k,近似计算出G中所有k-点连通分量(k-VCC)。在社会网络分析中,顶点连通度是衡量社会群体凝聚力的基本指标。给定一个无向图G,k-VCC是最大的连通子图其顶点连通度至少为k。一个k-VCC有着许多优异的结构特征,如鲁棒性,紧密型以及多样性。即使现有方法是多项式时间复杂度,但是在大规模网络分析中,时间开销非常高。在现有方法的框架上,笔者提出了一种基于概率采样的算法能够近似计算出G中所有k-VCCs。大量真实数据集的实验结果证明了近似算法的高效性和有效性。