谢家荣 博士论文

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

（2017年5月20日博士论文答辩会通过）

摘 要

在我们周围，复杂系统是普遍存在的。为了研究复杂系统，人们作了各种努力，建立了多种理论，而复杂网络是二十世纪末开始兴起的其中一种尝试。复杂网络是对复杂系统的一种抽象，这种抽象抓住了复杂系统的两个要点：个体与相互作用。这样做有以下三个好处：能将系统简化、降低系统的复杂度及维度；使得系统能用图论的数学语言描述，提供了一个直观的图像；为各种不同系统的研究提供了统一的框架。

复杂网络虽然是复杂系统的一种简化，但仍然很复杂，这就需要我们将维度进一步降低，从不同的侧面去观察网络。从不同的角度去观察和刻画复杂网络，能发现网络不同方面的特性，例如无标度特性、小世界特性等。而本文的研究重点，社团结构，是从大标度结构的角度刻画复杂网络。

社团结构是复杂网络的一种重要结构，本文对其重要性进行了总结，包括：社团结构有助于我们理解复杂网络的组织原理，社团结构在大量的真实网络中涌现，社团结构是连接网络结构与功能的一座桥梁，社团结构对网络其它结构的识别具有一定的作用，社团结构对网络的动力学行为有显著影响，社团结构提供一个观察网络的特定标度的视角，社团结构为一些算法提供一个验证的平台。

但是，对很多真实网络，我们往往只知道拓扑结构，而社团结构是未知的，这就需要我们对社团结构进行探测。为了进行社团结构探测，人们建立了多种方法，本文主要介绍了基于模块度的方法和统计推断方法两种。为了比较这些算法的性能，需要进行检测，通常是在具有参考分组的人工基准网络和真实网络中进行。在真实网络中，参考分组为领域专家基于网络的附加信息所给出，并且能被多种探测算法所恢复，这样的分组称为专家分组，往往被默认代表着网络的真实的社团结构，要求算法能将其恢复。尽管专家分组广泛使用于社团探测算法的检测，但很少有工作关注于专家分组本身的评估。

本文提出关于社团结构与专家分组之间关系的一个新的概念：完备性，即已知划分（不管是专家分组还是来自于社团探测算法）是否包含着网络社团结构的完整信息。为了研究这一问题，定义了一个关于社团结构的新的评价指标：排除模块度，并基于统计物理的空穴理论，建立一种具有数学原理的方法。本文发现，对空手道俱乐部网络，专家分组包含着网络社团结构的足够信息。而对于著名的政治博客网络，出人意料地，专家分组对社团结构的表达并不完备，说明还有隐藏在专家分组背后的未知结构，意味着社团结构与专家分组的关系需要重新检查。作为副产物，本文建立的方法还能用于探测隐藏的社团结构，在不删边的情况下发现层次性结构和获得网络的低维嵌套。

上述工作对专家分组的使用是将其从网络中排除，但有时，知道了节点的非拓扑属性可能会有助于社团结构的探测。基于这些已知属性，本文定义了类模块度目标函数，是经典的模块度与条件熵的线性组合。

另外，本文还介绍了作者在读期间的两个其它方向的工作。一个是复杂网络中基于行为响应的疾病传播，建立了网络中具有行为响应的传播模型，在平均场近似下使用渝渗方法，计算出了传播阈值和传播范围，与模拟结果能吻合。另一个是城市交通模型中的动态交通灯策略，提出了两种动态交通灯策略，其中一种比经典模型中的交替策略要好。

已发表论文：

1. Jia-Rong Xie and Bing-Hong Wang

Modularity-like objective function inannotated networks

Frontiersof Physics, 12(6), 128903 (2017).

2. Jia-Rong Xie, RuiJiang, Zhong-Jun Ding, Qi-Lang Li and Bing-Hong Wang

Dynamical traffic light strategy in theBiham-Middleton-Levine model

PhysicalReview E, 87, 022812 (2013).

3. Bin Zhou, Jia-Rong Xie,Xiao-Yong Yan, Nianxin Wang and Bing-Hong Wang

A model of task-deletion mechanismbased on the priority queueing system of

Barabási

PhysicaA, 466, 417 (2017).

4. Hai-Feng Zhang, Jia-Rong Xie,Han-Shuang Chen, Can Liu and Michael Small

Impact of asymptomatic infection oncoupled disease-behavior dynamics in complex

networks

EurophysicsLetters, 114, 38004 (2016).

5. You Zou, Jia-Rong Xie and Bing-Hong Wang

Evacuation of pedestrians with twomotion modes for panic system

PLoS ONE, 11(4), e0153388 (2016).

6. Rui-Jie Xu, Zhe He, Jia-Rong Xie and Bing-Hong Wang

Structure properties of adoubly-stochastic process on a network

PhysicaA, 445, 231 (2016).

7. Can Liu, Jia-Rong Xie,Han-Shuang Chen, Hai-Feng Zhang and Ming Tang

Interplay between the local informationbased behavioral responses and the epidemic

spreading in complex networks

Chaos, 25, 103111 (2015).

8. Hai-Feng Zhang, Jia-Rong Xie, MingTang and Ying-Cheng Lai

Suppression of epidemic spreading incomplex networks by local information

based behavioral responses

Chaos, 24, 043106 (2014).

9. Qi-Lang Li, Rui Jiang, Jie Min, Jia-Rong Xie and Bing-Hong Wang

Phase diagrams of heterogeneous trafficflow at a single intersection in a deterministic

Fukui-Ishibashi cellular automatatraffic model

EurophysicsLetters, 108, 28001 (2014).

10. Bin Zhou, Shujia Qin, Xiao-Pu Han,Zhe He, Jia-Rong Xie and Bing-Hong Wang

A model of two-way selection system forhuman behavior

PLoS ONE, 9(1), e81424 (2014).

11. 阚佳倩，谢家荣，张海峰

社会强化效应及连边权重对网络信息传播的影响分析

电子科技大学学报, 43(1), 8 (2014).

待发表论文：

1. Jia-Rong Xie, PanZhang, Hai-Feng Zhang and Bing-Hong Wang

Completeness of community structure innetworks

ScientificReports, revised.

2. Zong-Wen Wei, Hao Liao, Hai-FengZhang, Jia-Rong Xie, Bing-Hong Wang and

Guo-Liang Chen

Localized-endemic state transition inthe susceptible-infected-susceptible model

on networks

arXiv: 1704.02925.