复杂网络中的社团结构发现方法研究

摘要

实际应用中的很多系统都可以抽象成复杂网络,复杂网络是研究系统复杂性的重要模型和工具之一。社团结构是复杂网络最普遍、最重要的性质之一,它具有社团内部连接紧密、社团之间连接稀疏的特点。发现复杂网络中的社团结构对分析复杂网络的拓扑结构、理解其功能以及预测网络行为都具有重要的理论意义和广泛的应用前景。目前,社团发现在万维网、社会网、和生物网有着广泛的应用。
　　本文在分析现有社团发现算法的基础上,针对复杂网络研究中的几个热点和难点进行了相关的研究:一是复杂网络中的重叠社团的挖掘方法;二是无向权重复杂网络中的社团结构发现方法;三是复杂网络中的基于模块化函数Q值的社团挖掘方法。论文取得的主要成果如下:
　　(1)结合社团发现及聚类分析的相关研究,本文设计了一个基于网络社团结构和模块化函数的聚类算法。算法不仅能处理好“凹形”数据的聚类问题,而且能自动识别出聚类的类别数(网络中的社团个数)。算法在模拟和真实数据集上进行了实验研究,结果表明了算法的有效性。和其它典型算法相比,算法具有更佳的效果。算法不但可以用于聚类分析(社团发现),而且为有向权重网络的社团挖掘提供了思路;
　　(2)设计了一个基于模糊聚类的重叠社团发现算法。采用模糊熵函数计算网络中各节点在划分后的一个模糊程度,从而让重叠社团有的模糊程度的有了直观的表示,便于选取合适的阈值,对网络中的重叠社团进行合理地划分,实验在Zachary空手道俱乐部网络、海豚社会网络以及美国大学足球联赛网络这三个数据集上展开,实验结果表明,该算法能够很好地划分出网络中的重叠社区;
　　(3)在谱方法的基础上,结合模糊聚类算法,设计了一个基于谱方法的复杂网络重叠社团结构发现算法。针对Newman的Q指标存在分辨率极限的问题,设计了一个检测社团的有效指标D,该指标可以正确衡量社团划分的质量,且能避免Q指标分辨率极限问题;算法在Zachary空手道俱乐部网络、海豚社会网络以及美国大学足球联赛网络中进行了实验,另外通过泛化指标D,设计了一个针对模糊聚类中的阈值判定问题的方法,实验证明了该方法的有效性。
　　最后,本文分析了复杂网络中社团发现算法的未来发展方向。

目录

封面

中文摘要

英文摘要

目录

第1章 绪 论

1.1 引言

1.2 复杂网络的发展历史

1.3 复杂网络中的基本概念

1.4复杂网络中的社团结构

1.5 创新点和主要工作

1.6 论文结构

第2章 社团结构和社团结构发现算法

2.1社团结构的定义

2.2社团结构发现的研究内容和挑战

2.3社团发现算法

2.4本章小结

第3章 一种基于网络社团结构和模块化函数的聚类算法

3.1 引言

3.2 相关工作

3.3 基于模块化函数的聚类算法

3.4实验结果及分析

3.5 本章小结

第4章 一种基于模糊聚类的复杂网络重叠社团发现算法

4.1 引言

4.2 基于模糊聚类的重叠社团发现算法

4.3 实验结果与分析

4.4 本章小结

第5章 一种基于谱方法的复杂网络重叠社团结构发现算法

5.1 引言

5.2 基于谱方法的复杂网络重叠社团结构发现算法

5.3 实验结果及分析

5.4 本章小结

第6章 总结和展望

6.1本文总结

6.2 展望

参考文献

附录

致谢