摘 要:当今社会，大规模在线社会网络应用正在迅速发展.随着Facebook，Instagram等一系列社交网站的风靡全球，人们通过在线社会网络相互联系，形成了一个个内容丰富、关系复杂的社区.在社会网络中搜寻和发现社区，可以帮助人们更好的理解社会网络的演进过程和组织方式.目前，社会网络分析已经在商业领域得到了实际应用，但如何对大规模的社会网络进行快速高效地社区发现仍然是一个难题.因此，对于社会学者来说，分析社会网络的特征不仅有利于改善现有社会网络的应用，也有助于设计出更好的社会网络.

近年来，社会网络分析在职业流动、城市化对个体幸福的影响、世界政治和经济体系、国际贸易等领域获得了广泛应用并发挥了重要作用.本文将会通过对Zachary's Karate Club

成员关系数据源的拓扑结构的分析，来验证社会网络一般具有小世界模型以及个体中心性的特性，并对该网络运用Girvan-Newman 算法（G-N算法）进行社区划分，发现该俱乐部由于领导人的分歧逐渐演变成由俱乐部主席和教练分别领导的两个派系.在此基础上，再通过其他的网络数据，比如College Football和Political Blogs，对G-N算法进行验证.最后得出用G-N算法分析已知社区具有十分准确的优点，但是，当G-N算法被用于大规模社区划分时，耗时过久则是其不可避免的缺点.

关键词：在线社会网络; 社区发现; G-N算法; 社区特征分析

目录

摘要

ABSTRACT

第1章 绪论-1

 1.1研究的背景及意义-1

 1.2 目前研究现状-2

 1.3本文主要内容-2

第2章 相关技术与开发环境-5

2.1 社会网络分析简介-5

 2.2 UCINET简介-7

2.2.1 UCINET的运行环境-7

2.2.2 UCINET数据的输入-8

2.2.3 UCINET数据的处理-9

 2.3NetDraw软件简介-12

第3章 社会网络的拓扑结构-13

 3.1 拓扑结构的介绍-13

3.2 数据库的拓扑结构分析-15

 3.2.1途径长度均值的计算.15

 3.2.2 聚类系数的计算..21

第4章 社会网络的社区发现算法-23

 4.1 社区的理论基础-23

 4.2 社区发现的研究-25

4.2.1 社区发现概述-25

4.2.2 G-N算法分析-25

第5章扎卡里俱乐部的社区划分和分析-31

5.1 数据源-31

5.2 社区划分的结果-31

第6章 总结与展望-39

6.1本文工作的总结-39

6.2不足之处及未来展望-39

参考文献-41

致谢-43