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

作　　者：何瀛龙 王梦博 白雨 李源[1] 

机构地区：[1]北方工业大学信息学院,北京市100144

出　　处：《电子技术与软件工程》2022年第8期9-12,共4页ELECTRONIC TECHNOLOGY & SOFTWARE ENGINEERING

基　　金：国家自然科学基金青年项目(61902004)资助;北京市教委科技项目(KM202010009009)资助;国家大学生创新创业项目资助。

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

关 键 词：k-点连通分量 全局搜索 概率化算法 近似算法 

分 类 号：O157.5[理学—数学]