|||
谢家荣 博士论文
复杂网络中给予已知分组的社团探测方法
(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.
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-22 10:09
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社