题目：社交网络社区划分的传统算法改进研究

二十世纪九十年代，随着互联网的迅速发展，社交网络应用越来越受到人们的喜爱，用户数量也急剧增多。因此人们对社交网络的拓扑结构进行了大量的研究，其中社区结构是一个很重要的拓扑结构。通过研究人们发现，社交网络中普遍存在社区结构。目前为止，对于社区结构还没有一个比较统一而且普遍被人接受的定义。我们可以简单直观的认为，在社交网络中，社区内部的联系相对比较紧密，而一个社区和其他社区之间的联系则相对比较稀少。发现社交网络中的社区结构可以帮助我们挖掘社交网络中很多有用的信息，因此如何将一个社交网络划分成若干个社区结构具有很重要的现实意义。从二十一世纪初到现在，人们提出了很多的社区划分算法，常见的社区划分算法有基于图论的算法和基于层次聚类的方法。目前的社区划分算法中，有些算法需要预先确定社区的数目，有些算法的时间复杂度非常高，也有些算法检测出的社区与真实情况相差比较大。另外，对社交网络社区划分结果的有效性的评价没有一个统一的标准。目前的几个比较常用的评价标准也都有一定的局限性。

本文的主要贡献如下：

（1）类比于城市的层次结构，本文对社区结构提出了一个明确而且有效的定义；

（2）本文提出了一种基于层次聚类的社区划分算法（CDHC算法），从全局中心节点建立初始社区，再根据节点和社区的链接强度一层一层地扩展初始社区，最后把一些非常小的社区融合到大社区中。CDHC算法不需要预先知道社交网络中的真实社区数目，具有比较小的时间复杂度，可以方便地处理大型的社交网络，而且划分的结果比较好。

（3）本文在模块度的基础上提出了扩展模块度的概念，克服了模块度的一些缺点，可以更好地评价社区划分算法的有效性。

（4）本文通过实验验证了扩展模块度的优势，并且在常用的数据集上对比了CDHC算法和一些有代表性的社区划分算法，验证了CDHC算法的有效性和优势。