复杂网络的社团结构划分方法及其研究

摘要

信息技术的高速发展使人类社会大步迈入了网络时代，既有人们日常生活离不开的大型电力网络和交通网络,更有用于获取知识信息的Internet网络，万维网以及科研合作网络，人们已经生活在一个充满着各种各样的复杂网络的世界中。这些大规模网络的广泛存在，使得研究复杂网络成为必要，其中主要关注的是网络的拓扑结构以及网络上发生的动力学行为。特别是随着WS小世界网络模型和BA无标度网络模型的提出，吸引了更多科学家加入到对复杂网络的研究中。
　　 社团结构是许多实际复杂网络中的的一个重要特征。寻找和分析社团结构有助于更好地了解网络的内部结构，分析网络的性质。目前人们已经提出了很多算法用于寻找复杂网络中存在的社团结构。在本文我们将聚类分析方法引入到复杂网络中社团结构中进行研究。主要工作如下:
　　 1.介绍了复杂网络的基本概念及其基本性质包括度与度分布、聚集系数与最短路径、社团结构以及常见的两种网络模型。这些属性和网络模型是我们研究复杂网络的前提。
　　 2.综述了复杂网络中社团结构算法的研究历史及其意义，并且详细分析了寻找网络中社团结构的几种代表算法。其中主要包括社会学中的分级聚类和计算机图形学的图形分割两大类算法。这些方法将复杂网络划分成若干个节点较少，结构较简单的子网络，从而使研究较为简便。本文对这些典型的算法进行了介绍对其优缺点的也进行了分析，并引入聚类分析，简单介绍聚类的目的、意义以及目前常用的几种聚类方法。
　　 3.本文提出一种基于Normal矩阵的多维特征向量的社团划分算法，该算法在传统谱平分法的基础上，综合了多个特征向量的信息并结合数据挖掘中的聚类分析来判断社团的划分边界，尤其是多维特征向量的综合使得边界不是很清晰的社团也能够被较准确地划分出来。数据挖掘中的聚类分析算法，是分析社团结构的重要工具，在本文中采用了常见的几类聚类算法，并在仿真网络和真实网络中从初始敏感度、时间复杂度、和准确率三方面进行了实验对比，实验显示该方法相对其它复杂网络社团划分算法不仅对于社团结构明显的网络有效，而且在社团结构不明显的网络中也同样具有较高的划分准确率，同时实验中发现基于优化模块度Q函数的聚类类算法未必能找到真实网络的全部社团。

目录

文摘

英文文摘

声明

第一章 绪论

第二章 复杂网络中的社团结构

第三章 聚类方法综述

第五章 结论与展望

参考文献

附录

致谢

攻读硕士学位期间从事的科研项目及发表的学术论文