基于覆盖的社团发现算法

• 作者: 张燕平 段震 汪洋 赵姝 高兆远
• 来源期刊: 南京大学学报（自然科学版）
• 关键词: 复杂网络 社团发现 覆盖
• 年，卷（期）: 2013,（5）
• 页码范围: 539-545
• 语种: 中文

摘要

社团结构是复杂网络普遍存在的拓扑特性之一,发现复杂网络中的社团结构是复杂网络研究的基础性问题,近年来受到广泛关注,涌现出一批新颖的算法,但时间复杂度和准确率仍然是大规模复杂网络社团结构分析算法面临的两个主要问题.提出一种新的基于覆盖的社团发现算法,该算法的时间复杂度低,得到的社团结构准确率高,并且有效避免了一些经典算法无法识别小于一定粒度社团的问题.首先,以每个节点为中心构造覆盖,并提取其中的一部分覆盖以达到一定的覆盖率;其次,对提取的覆盖进行合并处理;最后,对重复覆盖和未覆盖到的节点做邻居节点投票划分.算法的时间复杂度为O(n2),实验部分测试了算法的准确率,并同标签传播算法(Label Propagation Algorithm,LPA)和Newman快速算法(NFA)作了比较.测试结果显示了本文算法的有效性,在已知社团结构的Zachary数据集上得到与实际完全一致的结果,在未知结构数据集上的Q值也高出LPA算法.