复杂网络社区结构划分算法研究

摘要

随着WS小世界网络模型和BA无标度网络模型的提出，国内外掀起了研究复杂网络的热潮。复杂网络的研究以系统的观点来看待真实系统，如Internet网络、电力网、新陈代谢网络等。复杂网络通常会呈现出社区结构特性，如何在实际网络中高效地发现社区结构是近年来复杂网络的研究热点之一。本文基于谱算法的思想提出了一种基于共邻矩阵和增益函数的有效算法来划分复杂网络中的社区，并把此算法推广到了加权的复杂网络中。主要工作如下： 1.定义了共邻矩阵和增益函数这两个概念，在此基础上提出一种有效算法来划分复杂网络中的社区结构。其中共邻矩阵中的元素定义为结点对之间拥有相同邻居的数目。以增益函数作为网络社区结构划分的目标函数，进一步推导出基于增益矩阵和增量矩阵的特征值和特征向量的社区结构划分方法。最后把这种算法应用于三个常用的实际网络数据中，并和Newman基于模块度矩阵的谱算法结果做了比较，以验证算法的可行性和有效性。 2.重新定义了在加权网络中结点对之间拥有共同邻居的数目，把基于共邻矩阵和增益函数的复杂网络社区划分算法推广到加权的复杂网络中。在以往许多复杂网络社区结构划分算法中，网络中的边常被看作是无权重的，但是现实世界中存在许多加权网络。如果忽略边的权重，仅仅把划分无权网络社区的算法应用到这些加权网络中，将会忽略许多包含在边权重中的重要信息，从而得出不尽合理的结果。借鉴Newman把加权网络映射到无权多重图的思想，重新定义了在加权网络中结点对之间拥有共同邻居的数目，然后将基于共邻矩阵和增益函数的算法推广到加权的网络中，并把算法应用到计算机仿真网络和实际的加权网络数据中，验证了推广算法的可行性和有效性。

目录

文摘

英文文摘

声明

1 绪论

1.1 复杂网络研究的背景与意义

1.2复杂网络社区结构研究现状

1.3本文的研究内容与文章结构

2复杂网络社区结构划分算法概述

2.1 复杂网络基本性质

2.1.1真实网络的图表示

2.1.2度分布

2.1.3 网络的平均最短路径和顶点的介数

2.1.4网络的簇系数

2.2复杂网络社区结构定义

2.3 复杂网络社区结构划分算法

2.3.1迭代二分法

2.3.2层次聚类法

2.3.3基于模块度矩阵的社区结构划分算法

2.3.4加权网络中的社区结构划分算法

3 基于共邻矩阵的复杂网络社区结构划分

3.1 引言

3.2共邻矩阵和增益函数

3.2.1共邻矩阵

3.2.2增益函数

3.3基于共邻矩阵和增益函数的社区结构划分方法

3.3.1 网络二社区结构划分方法

3.3.2网络多社区结构划分方法

3.4数值实验

3.4.1划分两个社区的应用实例

3.4.2划分多个社区的应用实例

3.5 小结

4加权复杂网络社区结构划分方法

4.1 引言

4.2加权网络到多重图的映射

4.3 加权网络中社区结构的划分

4.3.1加权网络中的社区结构

4.3.2基于共邻矩阵的加权网络社区结构划分算法

4.4数值实验

4.5 小结

结 论

参考文献

攻读硕士学位期间发表学术论文情况

致 谢