复杂网络中基于已知分组的社团探测方法

摘要

在我们周围，复杂系统是普遍存在的。为了研究复杂系统，人们作了各种努力，建立了多种理论，而复杂网络是二十世纪末开始兴起的其中一种尝试。复杂网络是对复杂系统的一种抽象，这种抽象抓住了复杂系统的两个要点:个体与相互作用。这样做有以下三个好处:能将系统简化、降低系统的复杂度及维度;使得系统能用图论的数学语言描述，提供了一个直观的图像;为各种不同系统的研究提供了统一的框架。
　　复杂网络虽然是复杂系统的一种简化，但仍然很复杂，这就需要我们将维度进一步降低，从不同的侧面去观察网络。从不同的角度去观察和刻画复杂网络，能发现网络不同方面的特性，例如无标度特性、小世界特性等。而本文的研究重点，社团结构，是从大标度结构的角度刻画复杂网络。
　　社团结构是复杂网络的一种重要结构，本文对其重要性进行了总结，包括:社团结构有助于我们理解复杂网络的组织原理，社团结构在大量的真实网络中涌现，社团结构是连接网络结构与功能的一座桥梁，社团结构对网络其它结构的识别具有一定的作用，社团结构对网络的动力学行为有显著影响，社团结构提供一个观察网络的特定标度的视角，社团结构为一些算法提供一个验证的平台。
　　但是，对很多真实网络，我们往往只知道拓扑结构，而社团结构是未知的，这就需要我们对社团结构进行探测。为了进行社团结构探测，人们建立了多种方法，本文主要介绍了基于模块度的方法和统计推断方法两种。为了比较这些算法的性能，需要进行检测，通常是在具有参考分组的人工基准网络和真实网络中进行。在真实网络中，参考分组为领域专家基于网络的附加信息所给出，并且能被多种探测算法所恢复，这样的分组称为专家分组，往往被默认代表着网络的真实的社团结构，要求算法能将其恢复。尽管专家分组广泛使用于社团探测算法的检测，但很少有工作关注于专家分组本身的评估。
　　本文提出关于社团结构与专家分组之间关系的一个新的概念:完备性，即已知划分（不管是专家分组还是来自于社团探测算法）是否包含着网络社团结构的完整信息。为了研究这一问题，定义了一个关于社团结构的新的评价指标:排除模块度，并基于统计物理的空穴理论，建立一种具有数学原理的方法。本文发现，对空手道俱乐部网络，专家分组包含着网络社团结构的足够信息。而对于著名的政治博客网络，出人意料地，专家分组对社团结构的表达并不完备，说明还有隐藏在专家分组背后的未知结构，意味着社团结构与专家分组的关系需要重新检查。作为副产物，本文建立的方法还能用于探测隐藏的社团结构，在不删边的情况下发现层次性结构和获得网络的低维嵌套。
　　上述工作对专家分组的使用是将其从网络中排除，但有时，知道了节点的非拓扑属性可能会有助于社团结构的探测。基于这些已知属性，本文定义了类模块度目标函数，是经典的模块度与条件熵的线性组合。
　　另外，本文还介绍了作者在读期间的两个其它方向的工作。一个是复杂网络中基于行为响应的疾病传播，建立了网络中具有行为响应的传播模型，在平均场近似下使用渝渗方法，计算出了传播阈值和传播范围，与模拟结果能吻合。另一个是城市交通模型中的动态交通灯策略，提出了两种动态交通灯策略，其中一种比经典模型中的交替策略要好。

目录

声明

摘要

表格索引

插图索引

主要符号对照表

第一章 绪论

1．1 引言

1．2 网络的表示

1．3 复杂网络的基本特性

1．3．1 度与无标度特性

1．3．2 最短路径与小世界属性

1．3．3 聚类系数

1．3．4 其它特性

1．4 网络模型

1．4．1 ER随机模型

1．4．2 随机分块模型

1．4．3 配置模型

1．4．4 BA模型

1．4．5 零模型

1．5 本文结构安排

第二章 社团结构及探测

2．1 社团与社团结构

2．1．1 社团结构涌现的原因

2．1．2 社团结构的表现形式

2．1．3 社团结构的重要性

2．2 社团结构的探测

2．3 基于模块度的方法

2．3．1 模块度的定义

2．3．2 模块度的限制及解决

2．3．3 模块度的变种

2．4 统计推断

2．4．1 基于SBM的统计推断

2．4．2 统计推断的变种

2．5 其它方法

2．6 算法的检测

2．6．1 评价指标

2．6．2 在人工基准网络中

2．6．3 在真实网络中

第三章 社团结构的完备性

3．1 排除模块度及BP算法

3．1．1 排除模块度的定义

3．1．2 统计物理的使用

3．1．3 BP算法的使用

3．2 在网络中的结果

3．2．1 在人工基准网络中

3．2．2 在真实网络中

3．2．3 其它应用

3．3 本章的相关推导

3．3．1 DCSBM与其变种的比较

3．3．2 排除自身划分的排除模块度

3．3．3 BP方程

3．3．4 顺磁相和自旋玻璃相间的相变点

3．3．5 biSBM的可探测阈值

3．4 小结与讨论

第四章 在读期间的其它工作

4．1 注释网络的类模块度函数

4．1．1 引言

4．1．2 方法

4．1．3 主要结果

4．1．4 本节小结

4．2 复杂网络中基于行为响应的疾病传播

4．2．1 引言

4．2．2 模型和分析

4．2．3 模拟结果

4．2．4 本节小结

4．3 城市交通模型中的动态交通灯策略

4．3．1 引言

4．3．2 模型和策略

4．3．3 中间态

4．3．4 本节小结

第五章 总结与展望

参考文献

致谢

在读期间发表的学术论文与取得的研究成果