复杂网络研究进展

复杂网络研究进展 王小云，邓 科∗∗，赵鹤平 （吉首大学物理科学与信息工程学院，吉首 416000） 摘 要：复杂网络的研究对于理解复杂系统的结构和行为至关重要．自从 1999 年 Barabási 和 Albert 发现真实 网络的无标度性质以来，有关真实网络中各种宏观性质的微观生成机制、网络的演化规律等一系列问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的研究 成为目前科学家广泛关注的热点．本文以网络度分布的微观生成机制为中心，介绍了其中的研究进展． 关键词：复杂网络；度分布；微观机制；网络演化 0 引言 ∗∗ 通讯作者，E-mail: dengke@jsu.edu.cn． 真实世界中存在的大量复杂系统可以通过网络 来描述[1-4]．网络由许多点（node）与连接两点间的 一些边（edge）组成，其中点用来代 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 组成真实系统 中的个体，而边用来表示个体间的相互联系．比如说， 人与人之间的社会关系，物种之间的捕食关系，词与 词之间的语义联系，计算机之间的网络连接，网页之 间的超级链接，科研文章之间的引用关系，以及科学 家之间的合作关系等都可以用网络模型来描述．复杂 网络是刻画和研究复杂系统的结构和行为的关键，近 年来，它迅速成为了科学界的一个研究热点，与之相 关的基础和应用研究已经渗入到物理学、生物学、计 算机科学、管理学、社会学以及经济学等许多学科之 中，在信息通信、网络搜索、信号传输、传染病控制 以及社会学中对突发事件的预报和处理等方面都具 有重要的意义． 网络研究的内容主要有三个方面．第一，定义各 种网络特征量来刻画真实复杂系统的宏观性质．第 二，建立网络模型以帮助人们理解真实系统中各种宏 观性质的微观生成机制．第三，研究在具有不同结构 的网络中发生的各种动力学过程的特征，比如研究流 行病的传播行为在无标度网络和指数网络中分别具 有什么特征等．目前，各国的研究人员已经在前两方 面的工作中取得了很大的进展，相对来说，第三方面 的工作仍处于起步阶段． 网络最初属于图论的研究范围．1736 年欧拉 （Euler）解决了著名的哥尼斯堡七桥问题，这标志 着网络研究的开始．早期图论主要涉及一些可以利用 简单规则网络来研究的问题，如数学上传统的 “一 笔画问题”、“邮递员问题”以及电路理论中对电路结 构的分析等．自上世纪五十年代以来，人们开始研究 一些大规模复杂系统的统计性质．但是，由于实验数 据的缺乏以及对数据统计分析的能力的不足，人们不 了解这些复杂系统的拓扑结构信息．当时人们将真实 复杂网络的拓扑结构看成是完全随机的，用随机网络 模型来描述它们．随机网络理论主要是由匈牙利数学 家 Erdős 和 Rényi（ER）创建[5]．在 ER 的随机网络 模型中，首先给定网络的点数，然后任意两点之间以 相同的常数概率连接在一起完全随机地构成网络．该 模型自提出以来一直在网络研究中扮演重要的角色， 被广泛应用于社会学和生态学的研究之中．近年来， 随着计算机技术的发展，对一些大规模的复杂系统进 行数据采集和统计分析变得可行．人们研究发现真实 网络的很多宏观性质不能被随机网络模型所刻 画．1998 年 Watts 和 Strogatz 发现的小世界性质 （small-world property）就是一个典型的例子[6]．该 发现在全世界范围内引发了复杂网络研究的浪潮并 标志着现代意义下复杂网络研究的开端． １ BA 模型 网络中某点的度（degree）被定义为与该点相连 接的边的数目．而网络的度分布 ( )p k 则给出在网络 中任意选出一个点其度值为 k 的概率．作为对网络进 行分类的首要依据[7]，度分布一直是网络最重要的特 征量之一．1999 年，Barabási 和 Albert（BA）[8]发现 许多真实网络具有幂律型度分布，即 ( )p k k γ−∼ ， 其中1 4γ< < （图 1）．Barabási 和 Albert 将这种网 络称为无标度（scale-free）网络．这一发现引起了网 络研究者的极大兴趣，人们开始思考导致这种宏观性 图 1 (A)电影演员合作网(B)万维网(C)美国西部电力网 具有幂律型度分布[8]． 图 2 BA 模型的度分布[8] 质的微观机制是什么．Barabási 和 Albert 认为，实际 网络中的这种 scale-free 现象来源于两个重要因素， 即增长机制和优先连接（preferential attachment）机 制．其中优先连接机制指的是一个新加入网络中来的 点与网络中已经存在的点建立连接的概率正比于这 些点的度值．基于这两个因素，Barabási 和 Albert[8] 提出了著名的无标度网络模型，后来被命名为 BA 模 型．该模型的定义如下： 在初始状态，网络包含 0m 个点，且没有任何的 边存在． (1) 在每一个时间步，一个新的点被加入到网络 中来，并与m （ 0m m≤ ，且为常数）个网络中已经 存在的点建立连接． (2) 新增加的点与网络中某点 i 进行连接的概率 i∏ 被假定为正比于点 i 的度值 ik ： i i j j k k ∏ = ∑ (1) 根据以上的规则，在经过 t 时间之后，可以得到 一个具有 0N t m= + 个点以及mt 条边的网络．研究 表明[8]，BA 模型中网络具有幂律型度分布（图 2）．该 模型为 scale-free 网络的出现提供了一种解释． BA 模型更重要的意义在于，它首次从演化的角 度研究网络一些宏观性质的起源，为网络研究开辟了 一条崭新的道路，由此奠定了网络演化模型的一般框 架；而且，该模型也使人们意识到真实网络的宏观性 质是由微观机制所导致的结果．自此，有关真实网络 中各种宏观性质的微观生成机制、网络的演化规律等 一系列问题的研究成为科学家广泛关注的热点． ２ 改进的 BA 模型 同在真实网络中得到的实验结果相比较，BA 模 型存在许多局限性．首先，在 BA 模型中网络具有不 变的幂指数（ 3γ = ），而所观测到的实际网络的γ 通 常在 1 到 4 的范围内取值[1]．此外，许多真实网络具 有其它形式的度分布，如被截断的（truncated）幂律 型度分布[9]和指数型度分布[10]等．这些事实说明真实 网络在演化过程还可能受到许多其它因素的影响，而 BA 模型没有考虑到这些因素．为了弥补这些不足， 在 Barabási 和 Albert 的网络演化模型的基本框架上， 许多研究人员提出了对 BA 模型的改进和推广，使该 模型能够对真实系统进行更好的刻画．下面我们对这 些改进工作做简单的介绍． ２.1 对于优先连接假设的改进 在对 BA 模型进行改进时，人们首先想到了用更 为一般的函数表达式来代替 BA 模型中的线性优先 连接关系式(1)．例如，在 Liu 等人[11]提出的一个改 进的 BA 模型中： i i j j k k α α∏ = ∑ (2) 研究表明，当 0 1α< < 时，该模型产生的网络 具有被截断的幂律型度分布． 对 BA 模型中优先连接假设的另一类改进方式 是引入所谓的初始吸引性（initial attractiveness）．这 是因为人们考虑到在真实网络中度值为零的点也有 获 得 边 的 可 能 性 ， 然 而 在 BA 模 型 中 ( )0 0i ik∏ = = ．如在 Dorogovtsev 等人[12]提出的一 个改进模型中，优先连接概率被修正为 0i ik k∏ +∼ ， 其中 0k 是常数，被称为初始吸引性因子．研究表明， 该模型具有幂律型的度分布，指数 03 k mγ = + 可以 被调节到与实验结果相符．由此可见初始吸引性能够 为真实网络具有各种不同的幂指数这一现象提供一 种可能的解释． Mossa 等人[9]则考虑了优先连接机制中的随机成 分．他们发现，当在 BA 模型中引进信息过滤 （information filtering）机制时，能得到具有被截断 的幂律型度分布和指数型度分布的网络． ２.2 局部事件的引入 对 BA 模型的改进还包括各种局部事件的引 入．例如，在 Albert 和 Barabási[13]的一个工作中，他 们考虑了加点、加边、重连三种事件．在每一时刻这 三个事件分别以概率 p 、 q 以及1 p q− − 发生．研 究结果表明具有指数可调节的 scale-free 网络和具有 指数型度分布的网络都可以由该模型产生，取决于 p 和q 之间的关系（图 3）． 图 3 网络度分布与 p 、q关系区间图． 1m = 时，图中 阴影部分代表网络具有 scale-free 度分布，其余部分则表示指 数型度分布； 0m → 时两区间的分界线由点线给出，m→∞ 时两区间的分界线则由虚线给出． Dorogovtsev 和 Mendes[14]研究了带有加边和去 边事件的网络的标度性质．他们发现，在一定的参数 范围内，模型所产生的网络仍然保持为 scale-free 的， 只不过其指数可以调节． ２.3 网络增长的限制因素 2000 年，Amaral 等人[7]在他们的一篇文章中提 出了将真实网络的度分布进行分类的思想．他们将真 实网络的度分布分为三类：幂律型度分布，被截断的 幂律型度分布以及单标度（single-scale）型度分布．考 虑到大多数真实网络的增长总是受到一定的限制， Amaral 等人在 BA 模型中引入了老化（aging）机制 和成本（cost）机制．他们发现，这两种机制中的任 意一种度分布都可以使网络的度分布偏离幂律形 式．在模型中，利用这两种机制，通过调节不同的参 数，他们得到了幂律型度分布，被截断的幂律型度分 布和指数型（图 4）． 图 4 由(a)老化机制和(b)成本机制得到的各种度分布[7] Dorogovtsev 等人[15]研究了逐渐老化（gradual aging）对网络度分布的影响，得出了与 Amaral 等人 类似的结果．此外，基于老化机制的思想，Klemm 图5 (a) C. elegans的神经网：指数型(b)影视演员合作网： 被截断的幂律型(c)摩门教教徒间和(d)417 名初中生间的相 识关系网：高斯型[7] 等人[16,17]在 BA 模 型 的 基 础 上 提 出 了 去 活 性 （deactivation）模型，该类模型产生的网络在保持 scal-free 的同时具有较高的团簇系数（clustering coefficient）． ３ AD 模型 2004 年，Deng 等人[18]在对大量已有的实验数据 进行仔细分析之后，将真实网络中各种度分布归纳为 五种类型：(1)幂律型度分布(2)被截断的幂律型度分 布(3)指数型度分布(4)被截断的指数型度分布[19](5)高 斯型度分布[7]（见图 5,6）；并提出了一种由加点事件 和去点事件构成的新型网络增长机制——AD 机 制．他们研究了在 AD 机制作用下的网络演化模型的 各种宏观性质，发现真实网络的五类度分布都可以由 该机制产生．在无优先连接机制的网络演化模型中， 他们得到了指数型度分布，被截断的指数型度分布以 图 6 某些食物网具有被截断的指数型度分布[19] 图7由 AD 机制生成的各种度分布[18](a)带有优先连接机 制的网络演化模型；(b)无优先连接机制的网络演化模型．其 中 Pa 为 AD 机制中加点事件发生的概率． 及高斯型度分布；在带有优先连接机制的网络演化模 型中，得到了幂律型度分布，被截断的幂律型度分布 以及指数型度分布．模型中，网络呈现何种度分布由 AD 机制中加点事件和去点事件发生的概率来决定 （图 7）．这些结果为真实网络中度分布的多样性提 供了一种较为合理的解释，并有助于揭示不同种类度 分布之间的一些内在联系． ４ 展望 复杂网络已经成为当今科学界研究的前沿和热 点．其研究者来自物理学、生物学、计算机科学、管 理学、社会学以及经济学等各个不同领域．美国科学 信息研究所（ISI）的统计结果表明，自 1998 年以来 该领域发表的研究论文数量以指数形式递增，大量关 于复杂网络的文章发表在 Nature，Science，PNAS， PRL 等国际一流的刊物上．网络的结构和性质、网络 宏观性质的微观生成机制、网络中的动力学行为是目 前本领域研究人员最为感兴趣的三个方向．网络研究 的前景极其广阔，特别是在以下几个方面有待人们进 一步的研究． 首先，对网络结构和性质的研究有待系统化．目 前用来刻画真实网络宏观结构的基本特征量主要有 度分布、平均最短距离（average path length）、团簇 系数[6]等．近年来又陆续提出了一些新的网络特征 量，如相关系数（correlation coefficient）[20]和介数 （betweenness）[21]等，力求更加详细和全面地刻画复 杂系统．然而，这些已有的特征量能否全面地刻画结 构非常复杂的真实网络？或者说，真实复杂系统是否 还具有其它更为重要的宏观性质没有被人们发现？ 如果有，那么如何定义特征量来刻画这些性质？这都 是值得进一步研究的，特别是需要实验研究的进一步 发展．比如说，最近大量的实验结果表明许多真实网 络具有分层结构（hierarchical organization）[1]．研究 指出[3]，处于不同层次的网络结构分别对应于真实系 统中不同的功能单元，如有机化合物分子结构中的官 能团．怎样定义特征量来刻画这种分层结构是当今颇 受人们关注的一个问题． 探寻网络各种宏观性质的微观生成机制一直是 网络研究中一项有意义且极富挑战性的工作．虽然现 在人们对于网络的无标度性质、小世界性质的微观生 成机制有了一定的认识，然而，对于度关联（degree correlation）[20]、团体结构（community structure）[1]、 分层结构等更为复杂的宏观性质的微观生成机制的 探索还刚刚开始，还需要人们进一步的努力． 研究网络中的动力学行为就是考察在具有不同 结构的网络中发生的各种动力学过程的特征．在此方 面人们已经开展了很多工作．比如说，对复杂网络中 流行病传播的动力学行为的研究近年来引起了研究 者的极大兴趣．研究表明[22]，对于无标度网络来说， 其传播强度阈值（epidemic threshold）趋于零，这就 使得在无标度网络中采用减小传播强度的方法并不 能够阻止传染病爆发．而对于结构化（structured）的 无标度网络而言[23]，传播强度阈值不为零．那么，如 何针对不同结构的网络 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 行之有效的免疫策略成 为网络研究中一个重要的问题．此外，对不同结构复 杂网络鲁棒性（robustness）以及脆弱性（vulnerability） 的研究 也是一个具有极其广泛应用价值的课题．研究 指出[24,25]，由于集散节点（hub）的存在，无标度网 络对于随机性的故障和错误有较强的鲁棒性，而对于 选择性的攻击则体现出其脆弱性的一面．如何系统的 研究大规模真实复杂系统的鲁棒性和脆弱性则被视 为当今复杂网络研究中十个最重要的问题之一[26]． 在过去的短短几年中，复杂网络研究的发展非常 迅速．一方面，理论上不断给出新的模型和结论对已 有的实验数据提供了解释；而另一方面，实验上不断 观察到的新现象也为理论研究人员提供了新的挑战 和机遇！复杂网络研究方兴未艾，网络研究者任重而 道远． 参考文献： [1] Albert R., Barabási A. L. Statistical mechanics of complex networks[J]. Rev. Mod. Phys., 2002, 74: 47-97. [2] Dorogovtsev S. N., Mendes J. F. F. Evolution of networks[J]. Adv. Phys., 2002, 51: 1079-1187. [3] Strogatz S. H. Exploring complex networks[J]. Nature, 2001, 410: 268-276. [4] Newman M. E. J. The structure and function of complex networks. SIAM Review, 2003, 45: 167-256. [5] Erdős P., Rényi A. On random graphs[J]. Publ. Math. Debrecen, 1959, 6: 290-297. [6] Watts D. J. , Strogatz S. H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998, 393: 440-442. [7] Amaral L. A. N., Scala A., Barthélémy M. et al. Classes of small-world networks[J]. Proc. Natl. Acad. Sci. U.S.A., 2000, 97: 11149-11152. [8] Barabási A. L., Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286: 509-512. [9] Mossa S., Barthélémy M., Stanley H. E. et al. Truncation of power law behavior in “scale-free” network models due to information filtering[J]. Phys. Rev. Lett., 2002, 88: 138701. [10] Camacho J., Guimerá R., Amaral L. A. N. Robust patterns in food web structure[J]. Phys. Rev. Lett., 2002, 88: 228102. [11] Liu Z. H., Lai Y. C., Ye N. Statistical properties and attack tolerance of growing networks with algebraic preferential attachment[J]. Phys. Rev. E, 2002, 66: 036112. [12] Dorogovtsev S. N., Mendes J. F. F., Samukhin A. N. Structure of growing networks with preferential linking[J]. Phys. Rev. Lett., 2000, 85: 4633-4636. [13] Albert R., Barabási A. L. Topology of evolving networks: local events and universality[J]. Phys. Rev. Lett., 2000, 85: 5234-5237. [14] Dorogovtsev S. N., Mendes J. F. F. Scaling behaviour of developing and decaying networks[J]. Europhys. Lett., 2000, 52: 33-39. [15] Dorogovtsev S. N., Mendes J. F. F. Evolution of networks with aging of sites[J]. Phys. Rev. E, 2000, 62: 1842-1845. [16] Klemm K., Eguíluz V. M. Highly clustered scale-free networks[J]. Phy. Rev. E, 2002, 65: 036123. [17] Klemm K., Eguíluz V. M. Growing scale-free networks with small-world behavior[J]. Phy. Rev. E, 2002, 65: 057102. [18] Deng Ke, Tang Yi. Growing networks based on the mechanism of addition and deletion[J]. Chin. Phys. Lett., 2004, 21: 1858-1860. [19] Dunne J. A., Williams R. J., Martinez N. D. Food-web structure and network theory: the role of connectance and size[J]. Proc. Natl. Acad. Sci. U.S.A., 2002, 99: 12917-12982. [20] Newman M. E. J. Assortative mixing in networks[J]. Phys. Rev. Lett., 2002, 89: 208701. [21] Goh K. I., Kahng B., Kim D. Universal behavior of load distribution in scale-free networks[J]. Phys. Rev. Lett., 2001, 87: 278701. [22] Satorras R. P., Vespignani A. Epidemic spreading in scale-free networks[J]. Phys. Rev. Lett., 2001, 86: 3200-3203. [23] Eguíluz V. M., Klemm K. Epidemic threshold in structured scale-Free networks[J]. Phys. Rev. Lett., 2002, 89: 108701. [24] Albert R., Jeong H., Barabási A. L. Attack and Error Tolerance of Complex Networks[J]. Nature, 2000，406: 378-382. [25] Wang X. F., Chen G. Synchronization in scale-free dynamical networks: Robustness and fragility[J]. IEEE T Circuits-I, 2002, 49: 54-62. [26] Amaral L. A. N. et al. Virtual Round Table on ten leading questions for network research[J]. Eur. Phys. J. B, 2004 38: 143–145. A Brief Review to the Study of Complex Networks WANG Xiao-yun, DENG Ke, ZHAO He-ping (College of Physics and Information Engineering, Jishou University, Jishou 416000) Abstract: Complex networks play a key role in the understanding of the structures and behaviors of complex systems. In 1999, Barabási and Albert found that many real-world networks exhibit the scale-free property. Since then, the exploration of the corresponding microscopic mechanisms leading to the macroscopic properties of real systems, as well as the investigation of the law of network evolution, etc, has attracted considerable interest in the scientific community. Focusing on the studies of the microscopic mechanisms leading to the degree distribution of networks, we review the process in this field. Keywords: complex networks; degree distribution; microscopic mechanisms; network evolution