复杂网络的SCALE-FREE性、SCALE-FREE现象及其控制

摘要

复杂网络是复杂系统的高度抽象，在现实世界中存在大量的复杂网络。自从1998年、1999年在“Nature”和“Science”两个刊物上发表了关于小世界网络和Scale-free网络的两篇文章以来<'[8,32]>，在世界范围内掀起了一股复杂网络的研究热潮。究其原因是因为过去关于复杂网络的一些重要结论是不妥的，而今开始了崭新的研究。 此后几年来，关于复杂网络的研究取得了一批重要成果，包括大多数实际网络中的Scale-free性质的发现、复杂网络的Scale-free性质对于传播动力学和同步动力学的深刻影响、复杂网络上的社区发现、复杂网络的演化等等。更令人感兴趣的是，研究发现，复杂网络的许多研究成果可以直接应用于实际复杂系统，如Scale-free网络中病毒传播的特殊机制，以及据此而对传统病毒防治模式的改进。总之，复杂网络的重要性已得到了世界范围内有关领域科学家的深切关注。 然而，毕竟是刚刚起步，关于复杂网络的研究还很不充分，远没有形成属于本方向系统的、独特的研究方法。如复杂网络的拓扑结构的刻画、复杂网络的异质性的刻画、异质性如何影响复杂网络上的动力学、复杂网络上的SIS模型的全局稳定性、SIS模型中最终感染节点的比例、复杂网络上的SIR模型中病毒爆发的规模如何受到拓扑结构的影响、复杂网络中度分布指数的变化范围为什么一般位于2～3之间以及复杂网络中的控制问题等等方面的研究，是非常不够和初步的。我们正是针对上述诸问题进行了全面而深刻的研究，综合运用了严谨的数学方法和计算机仿真手段，历经3年时间，取得了如下主要成果： (1)提出了复杂网络中的连接率和吸引率的新概念，并应用于Internet网络。利用我们所提出的静态概率模型，从理论和实证两个方面证实了：a)Interaet网的子网的连接率服从幂律分布；b)Internet网存在网络核心(Core)；c)作为一个推论，发现度分布指数存在一个临界点为2。 (2)将经济学中的洛仑兹曲线与基尼系数引进到复杂网络以刻画复杂网络的异质性，通过与复杂网络的其它参数(度分布指数、网络结构熵、度分布熵等)进行比较，发现基尼系数是刻画复杂网络异质性的一个合理指标。 (3)从理论上对Scale-free网络的度分布指数进行了研究，揭示了现实世界中大多数网络的度分布指数位于2～3之间的理论根由，从而回答了Barab6si在文献[9]中提出的疑问。研究了Scale-free网络中Hub点的若干独特性质，如Hub点的数量、Hub点的最高度值等问题，发现了度分布指数与Hub点之间的关系，并首次给出了Hub点的量化定义。 (4)针对BBS这样一个具体的复杂网络的Scale-free性质进行了实证研究，发现BBS用户网络的结构与针对某一个特定话题的BBS用户网络的结构存在本质的区别：前者的度分布指数小于2，后者的度分布指数大于2。这说明特定话题的BBS用户网络仅存在极少量的Hub节点，这一结论有利于对重点用户进行跟踪。此外，还将复杂网络中的社区结构及其发现算法成功地应用于BBS的热点发现，仿真结果表明，热点发现的效率大大提高。 (5)深入分析了Scale-free网络上的SIS模型的全局稳定性问题，发现只要传播强度大于阈值，不管初始感染比例多么地小，网络最终感染节点的比例是一定的。 探讨了网络最终感染节点的比例以及阈值与网络度分布指数之间的关系，发现度分布指数越小，则阈值越小，并且网络最终感染节点的比例越大。这一结论给Scale-free网络上的病毒防治提供了一个新的思路。 (6)深入分析了Scale-free网络上的SIR模型的病毒爆发问题。由于SIR模型下，最终感染节点均消失，故研究的问题是少数感染节点是否会引起大量节点被感染，即病毒爆发问题。我们从理论上发现，存在病毒爆发的阈值。 探讨了网络中病毒爆发的规模(即曾经感染过病毒的节点的比例)与度分布指数之间的关系，发现度分布指数越小，病毒爆发规模越大。 (7)研究了Scale-free网络中的控制问题，提出了Scale-free网络中反馈控制的一般性框架。在此基础上提出了互联网拓扑结构的一个新的演化控制模型，通过调整某些参数，该模型能够演化出多种类型的网络，并且能够再现互联网的某些动态特征，如互联网的Hub点的形成时间等。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究的背景及意义

1.2国内外研究现状

1.3研究内容及论文框架

1.4本文的主要创新点

第二章复杂网络的两个拓扑参数

2.1引言

2.2连接率

2.3吸引率

2.4复杂网络的一个静态概率模型

2.5定理2.1的证明

2.6小结

第三章复杂网络的异质性指标

3.1引言

3.2度分布指数

3.3网络结构熵

3.4度分布熵

3.5洛仑兹曲线与基尼系数

3.6异质性指标的比较

3.7小结

第四章Scale-free网络的拓扑结构及其形成机制

4.1引言

4.2度分布指数的取值范围

4.3 Scale-free网络中的Hub节点

4.3.1 Scale-free网络中的最高度值

4.3.2 Scale-free网络中的Hub节点的量化研究

4.4 Scale-free性质的形成机制

4.5小结

第五章BBS网络的Scale-free性质及其社区发现

5.1引言

5.2 BBS网络的Scale-free性质

5.3复杂网络中的社区结构及其发现算法

5.4复杂网络中的社区发现在BBS热点话题发现中的应用

5 5小结

第六章Scale-free网络的鲁棒性

6.1引言

6.2静态鲁棒性

6.3雪崩动力学

6.4小结

第七章Scale-free网络上的传播动力学-SIS模型

7.1引言

7.2复杂网络中SIS模型的平衡点的若干性质

7 3复杂网络中SIS模型的解的若干性质

7 4复杂网络中SIS模型的稳定性分析

7 5复杂网络中SIS模型的收敛速度分析

7.6 Scale-free网络中SIS模型的感染规模分析

7.7 小结

第八章Scale-free网络上的传播动力学-SIR模型

8.1引言

8.2任意连接边指向移除节点的概率

8.3若干引理

8.4复杂网络中SIR模型的病毒爆发的阈值

8.5复杂网络中SIR模型的病毒爆发规模分析

8.6 小结

第九章Scale-free网络上的同步动力学

9.1引言

9.2复杂网络中的同步

9.3主稳定函数法

9.4网络的异质性对于同步的影响

9.5小结

第十章Scale-free网络中的控制

10.1引言

10.2一般性框架

10.3互联网拓扑结构的演化控制模型

10.4 小结

第十一章结束语

11.1本文的主要研究结论

11.2后续工作与发展方向

参考文献

攻读博士学位期间研究工作简介

致谢