复杂网络社团结构发现算法研究与实现(3)

菜单

1 引言（或绪论） 1

1.1 研究背景1

1.2 国内外发展现状1

1.3 论文结构3

2 相关算法分析 4

2.1 算法衡量标准 4

2.1.1 模块性 modularity 4

2.2 群聚算法的比较 6

2.2.1 GN 算法 6

2.2.2 Clauset, Newman, Moore 社团侦测算法 7

2.2.3 另一个典型的凝聚算法 10

2.3 总结 13

3 社团结构发现算法 15

3.1 设计原则 15

3.2 设计模型 16

3.3 新的算法 16

3.3.1 选择衡量标准及算法执行方式 16

3.3.2 确定分类依据和粒度控制 18

3.3.3 确定算法执行步骤 19

3.3.4 优化数据结构 20

3.3.5 算法相关测试 21

4 结论 26

致谢 27

参考文献28

1 引言 1．1 研究背景 2002年，M. Girvan 和 M. E. J. Newman首次在现代ᨀ出了网络社团具有团内联系紧密，团间联系松散这一性质[1]，由此引发了研究网络社团结构的热潮。许多自然中的复杂系统都呈现出模块状结构——它们对外展现为由独立部分所连接的状态［12］。如果用图表示这些系统，它们的基本元素被᧿述为节点之间的交互和连接。我们把这些由图表示的系统成为网络，节点呈现出的分组结构称为社团。社团挖掘实则属于交叉领域，它的主要目标是利用计算机中图的相关知识去分析其他领域中的复杂系统。侦测社团结构的能力具有明显的实际应用价值。比如，侦测到的社团在社会网络中可能代表一个真实的群体（这些群体可能因为兴趣或者社会背景等因素而形成）。再比如，在文献引用的网络中探测到的社团可能代表拥有相似题目的相关论文 [1]。又例如，在生物网中侦测到的社团可能代表一个小的生物圈或者群落。总之，社团分类已成为交叉学科里最热门的领域之一［11］，它已广泛应用于社会学、计算机图形学、物理学和生物学等领域[2]。今天，大型社交网站（如Facebook）的流行又赋予了社团结构分析更多样更广泛的应用价值和意义。
1．2 国内外研究现状近几年，相关的学者对社团发掘做出了大量研究。这其中包括对社团发掘算法的设计，对算法衡量标准的研究以及对算法应用的拓展。社团挖掘算法主要分为传统的图像分区(graph partitioning)算法和群聚(clustering)算法[3]，其中群聚方法是今年来进展较多的地方。群聚算法主要分为凝聚算法和分离算法，二者本质类似。分离算法的思路是根据某种法则从已有网络中移除边（或者点），使得网络被分割成小的社团。第一个社团分类算法是典型的分离算法源]自=751-^论-文"网·www.751com.cn/ ，它于 2002年，M. Girvan 和 M. E. J. Newman ᨀ出[1]，简称GN算法。凝聚算法则相反，它的思路是将所有的点均看作社团，依据某种法则不断地合并社团，最终实现社团分类。典型的社团凝聚算法有Newmanᨀ出的FastGN[4]，Clauset, Newman, Moore社团侦测算法[5]，Vincent