无标度网络：基础理论和应用研究

史定华

(上海大学数学系 上海 宝山区 200444)

20世纪末21世纪初，《自然》和《科学》相继发表了3篇重要的关于网络的文章：小世界网络模型[1]说明了少量的随机捷径会改变网络的拓扑结构，从而涌现出小世界效应；无标度网络模型[2]揭示了增长和择优机制在复杂网络自组织演化过程中的普遍性和幂律的重要性；可导航网络模型[3]则解释了如何利用局部信息寻找网络中的最短路径。这些模型说明复杂系统也可由某些简单规则自组织演化而形成。

复杂网络理论与应用发展至今已十余年，其轰动效果和强烈冲击很大程度上归功于《自然》和《科学》上的一系列开创性论文[2,4-7]。虽然这些论文的思想新颖动人，但也留下了广阔的发展空间。为了复杂网络理论与应用的健康发展，本文基于文献[8]，逐一展开讨论，说明加强基础理论和应用研究的重要性。对无标度网络过去十年的发展情况及未来前景，文献[8]要点总结如下：

(1) 通过对万维网结构调查得到的情况指出网络并非都是随机连线，而是显示出增长和择优连线两种机制，这恰是使得网络产生幂律度分布的可能的原因。

(2) 许多真实的网络系统，从细胞到因特网，都收敛到类似的(度分布为幂律)结构上，而与它们的年龄、方式和规模等无关。

(3) 无标度特性的意义之一在于认识到网络的结构和演化不可分割，即真实的网络是动态的而非静态的，网络处在不断的变化之中。

(4) 在无标度网络(如因特网等)中，网络整体的连通性对节点随机故障的鲁棒性以及hub nodes易受蓄意攻击而遭到大规模破坏具有“稳健而又脆弱”的特性。

(5) 从度分布到度−度相关性等等，不同网络拓扑特征的广泛存在被作为研究不同现象以及作出预测的跳板，除非探讨网络拓扑，否则无法理解复杂系统。

(6) 需要攻克的下一个前沿问题是理解在网络上发生的动力学过程。共性是存在的，只是还没有发现能够解释网络动力学的普适框架。

(7) 虽然复杂系统的许多研究热潮来了又走，但是有一件事日益清楚，即单元之间的相互连接(作用)如此重要，这正是现今关注网络的原因。

本文将分5个小节展开讨论。

1 BA模型和万维网因特网

一系列开创性论文中，文献[2]尤其引人关注。论文的主要思想有：从许多实际复杂网络度分布的统计结果发现，具有幂律尾部是其普遍的特征；提出一个择优增长的动态模型(即BA模型)去解释产生幂律的机制；认为正确的模型其网络度分布应该独立于时间。从此，具有幂律度分布的网络被称为无标度(scale-free)网络。然而，该文存在某些不够完善之处。

首先，文献[9]指出BA模型有两点不够明确：一是初始网络没有设定，孤立节点无法择优连线；二是有多条连线时如何进行择优连接，是一条一条连线还是同时连线？前者择优概率会改变，后者度分布结果大相经庭。所以，模型定义不明确将难以开展理论研究。为此，文献[9]提出了同时允许节点自连线和节点之间重复连线的线性化弦图(linearized chord diagram)模型。通过允许节点之间重复连线但不允许节点自连线，文献[10]引入了一个原始吸引模型避免BA模型连线的不明确。为了提高BA模型的群集系数，文献[11]提出了一种不允许重复连线的方式：第1条连线按节点度择优连接，其余m−1条连线在被第1条连线选中节点的邻域依次不重复连线。

利用鞅论和马氏链等数学理论已经严格证明：上述3个模型都具有与BA模型用启发式方法得到的相同度分布。

其次，文献[12]认为仅以度分布是幂律作为无标度网定义不尽合理。一方面，网络拓扑除了度分布外还有度−度相关性等许多测度；另一方面，因为幂律是方差可能无穷的高可变分布，由于存在极大的波动性，所以幂律相同的度分布网络完全可能具有极其不同的拓扑结构和特性。该文献从度−度相关性引入一个测量无标度程度的量，发现对具有相同幂律度分布的网络，有的显示为“无标度”，有的却显示为“标度丰富”。因特网和代谢网的度分布虽然为幂律，但却是标度丰富的两个典型案例，它们面对蓄意攻击仍然“稳健而非脆弱”。文献[13]针对因特网进行详细解释，同时说明BA模型不是因特网的恰当模型，从流量、带宽以及技术可靠等设计角度提出了一个启发式最优拓扑模型。

其中，度指数相对网络规模稳健，系数需要重点探讨。

用模型网络的度分布预测实际网络高度数的概率时会严重偏离或失效，文献[16]提出研究有限标度问题，发现有限标度函数会显著地依赖于初始网络。许多研究工作[17-18]报道了网络动力学行为也依赖于网络规模的大小。另外，万维网和因特网的连线增长明显快于节点增长[19-20]，同样，BA模型也不是万维网和因特网的合理模型。复制模型[15]的平均度对数增长，文献[14]提出的饱和模型增长有个上限，或许它们才是更恰当的模型。

2 层次网络模型和代谢网络

文献[8]虽然没有提及代谢网络和层次组织两篇开创性论文[5-6]。但文献[5-6]统计了大量的代谢网络，发现它们是无标度的，度指数接近2.2以及群集系数与度k存在反比关系。生物网络是复杂网络最重要的应用领域之一，为了给代谢网络建立恰当的模型，Barabási等人提出了确定的层次网络模型。然而层次网络、伪分形图、阿波罗网等几何增长网络的度分布和度指数在文献上就一直是颇有争议的问题。该问题还与实际网络度分布的统计有关，因此值得在此讨论。

文献[21]提出了第一个确定性的层次网络，得到该模型网络的度分布为：

其实，正确的答案文献[12]早就给出。关于幂律和标度首先要有一个正确的定义，文献[12]对确定的和随机的两种情况都有详尽的论述。几何增长网络和实际网络数据都属于确定的情况，复杂网络文献判断度分布和度指数有画频率图、画logarithmic binning图、画秩次(或类同的补分布)图3种方法。秩次图是以秩次为纵坐标，将N个节点的度从大到小排序，依序给予从1～N的秩次所画的图。在双对数坐标上，如果图形近似为一条直线，就认为是幂律；负的斜率为度指数，秩次(补分布)方法需要加1。显然，频率方法忽略了频率为零的度，结论容易误导；logarithmic binning是一种粗粒化方法，也不可靠；正确的方法是画秩次图。所以几何增长网络正确的度指数应该加1才对。另外，文献[27]论述了代谢网是标度丰富的，因此层次网络不是代谢网的恰当模型。

3 无标度网络的动力学特性

文献[7]是第一篇动力学文献。通过模拟比较了ER随机图和BA无标度网对节点删除的影响。考虑两种节点删除方式：一是某些节点随机失效；二是蓄意攻击hub nodes。对10 000个节点20 000条连线，横坐标f表示删除节点比例，纵坐标d表示网络直径变化，结果如图1所示。

图1 指数网络与无标度网络其直径d关于f的曲线[7]

从图1可以看出：对ER随机图，随机失效和蓄意攻击没有区别；但对无标度网络，随机失效和蓄意攻击显著不同。如何解释这种动力学性质的差异？文献[7]认为是ER随机图节点同质而BA无标度网节点异质，即存在hub nodes所致。该期《自然》杂志还特别在封面用标题为《因特网的Achilles踵(heel)》的文章对此发现做了介绍。Achilles是古希腊传说中的一位杰出英雄，但他的脚后跟与普通人一样存在致命弱点。换句话说，Achilles踵也就是中国武功的“罩门”。能找到复杂网络的罩门，对网络科学当然意义重大。

这里有两个问题需要认真思考，一是“稳健而又脆弱”是否为无标度网的普适特性？二是究竟什么原因造成复杂网络对蓄意攻击脆弱？关于第一个问题，文献[12]给予了否定的回答。然而，第二个问题的回答就没有那么简单。是不是因为存在hub nodes，即度数很大的少数节点，答案显然不全面，因为任何有限网络都存在最大度节点。而是否与这些hub nodes的连接方式有关，将在下一小节讨论。值得一提的是，文献[28]对类似于BA模型的LCD模型，用数学方法就第二个问题进行了严格的理论证明。证明篇幅长达35页，主要结论是：BA无标度网络比ER随机图更稳健而又更脆弱的主要原因是由于择优连线。

网络动力学的另一个重要发现[29]是：在无标度网络中，传染病的传播阈值收敛于0。这只是对BA无标度网络得到的理论结果，因为实际网络都是有限网络，需要考虑网络有限规模的影响[16]。文献[17]最近发现，无标度网络的动力学模型有两类不同的有限网络影响，一类只依赖有限网络的规模N(等于模拟步数t加m0)；另一类同时依赖有限网络的规模N和上割kc。

4 网络核心和度−度相关性

文献[12]认为hub nodes的连接方式决定了度分布为幂律的网络对蓄意攻击是否脆弱。文献[12]绘制了4个路由器层次因特网模型的网络如图2所示。

图2 具有完全相同数目的节点、连线和幂律度分布的4个路由器层次因特网模型

它们具有完全相同数目的节点、连线及幂律度分布，但带宽(灰度深浅)却不同。HSF(无标度层次)网是基于文献[6]的层次网络模型；随机(重连)网是从HSF通过保度重连得到的。拙劣设计网是将高度节点排成一条线，然后让低度节点与高度节点连线；HOT(启发式最优拓扑)网有3层结构，高带宽低连通节点位于核心，而低带宽高连通节点位于外围。从图中可以看出，图2a和图2b具有网络核心，它们的高度数节点倾向于相互连接，即所谓网络节点同配；图2c和图2d不像具有网络核心，因为它们的高度数节点倾向于连接低度数节点，即网络节点异配。文献[13]的详细研究说明：实际的因特网并不像HSF网，至少在定性上像HOT网。文献[12]计算了该4个网络的Newman相关系数r(g)[32]，然而，所得的数值都落在区间[−0.481 5, −0.428 3]中，不足以区分。为此该文献提出了一个无标度程度新测度。

对BA模型通过模拟和计算得到r(g)和S(g)的结果如图3所示。

图3 r(g)和S(g)分别关于m和N的趋势[33]

不难发现，r(g)和S(g)都显著地依赖网络的规模和网络的平均度，所以这两个测度对有限的实际网络很难给出一个有意义的数值。另外，从图3b可以看出，BA模型的无标度程度也不能算大，但它面对蓄意攻击却是“稳健而又脆弱”！

因此，本文同意文献[8]的观点：“除非(深入)探讨网络拓扑，否则无法理解复杂系统”。网络度−度相关性的完整信息包含在网络联合度分布中，目前文献上只有BA模型的部分结果[34]，还没有像度指数(或动力学指数)那样简便的最佳测度。

为此，以网络平均度为分界线，按度将节点分成大度和小度两类，同类节点连线称为同配，异类节点连线称为异配，通过计算同配、异配数目，文献[33]尝试提议了一个简单的测度，模拟显示对BA模型能做到与网络规模无关。而且该测度与网络疏密程度存在幂律关系，直观上，网络的疏密程度与网络的抗毁性有关，所以网络核心与网络疏密程度有关应该是合理的。

5 网络马氏链(图值马氏过程)

复杂网络十年来的发展和成就毋容置疑，涉及领域的广泛也使个人无法全局把握。其中物理学家的思想火花绚丽无比，物理社团的大力推动也功不可没。前面对复杂网络的讨论负面评价较多，本节介绍复杂网络中主观认为的两个正面结果：一个是复杂网络信息检索，属于应用研究范畴；另一个是模型网络度分布证明，属于基础理论领域，两者都与网络马氏链或称图值马氏过程有关。

在谷歌中输入“荷塘月色”，马上会出现许多条目，有朱自清的散文“荷塘月色”，有各种美丽的荷塘图片，甚至会出现荷塘春色和可爱的青蛙形象，如图4所示。人类上网冲浪就像青蛙在荷页上跳动，而马氏链可以形象地用“荷塘春色蛙欢跳”来描述。“荷塘月色”可比喻为隐马氏模型，只闻蛙声，不见蛙跳，在生物信息学中有广泛应用，如图5所示。

谷歌为什么会有如此强大的功能？它的原理依赖于复杂网络的拓扑和数学中的马氏链。根据论文引用和被引用的思想，文献[35]完成了网络搜索和存储，剩下寻找为网页评定等级的方法。他们发明了一种基于网页重要性的排序算法：一是看有多少超级链接指向它(入度)；二是要看那个页面重要不重要(出度)，并命名为PageRank。因此，问题可归结到求有向图连线矩阵的非负特征向量，最后转变为计算有限马氏链的平稳分布。值得一提的是，文献[36]当时正好提出了中心网页和权威网页的评级系统，他们交流了各自的工作。该文作者由于提出可导航网络模型和分散搜索算法，2006年获得了世界数学家大会三大奖之一的Nevanlinna奖。

谷歌搜索引擎虽然取得了巨大成功，但排序只依赖页面的连线(度)，因此会面临垃圾网站的严重干扰。文献[37]针对上述情况在2008年原创性地提出考虑用户浏览过程的网页排序，并把他们的算法取名为BrowseRank。根据用户访问网页和网页转移的频率数据qi和qij得Q-过程的转移概率矩阵P=[qij/qi]，使问题转化为求Q-过程的平稳分布。他们的论文被评为当年ACM会议唯一的最佳学生论文奖，国际媒体用标题“Microsoft tries to one-up Google PageRank”做了报道。

图4 马氏链示意图

图5 隐马氏链示意图

上述复杂网络信息检索工作，大家天天都在受益，堪称复杂网络成功应用的典范。

6 结 束 语

复杂网络在发展过程中存在欠妥并不可怕，贵在勇于修正错误，因为科学本身就被设计成寻找并改正错误的过程，即科学的完整性(the integrity of science)。

通过对文献[8]“无标度网络：过去十年及未来前景”一文的探讨，即使在复杂网络拓扑方面仍然有许多问题需要理清。至于复杂网络动力学方面，本文同意Barabási的观点：“(只是)还没有发现能够解释它们普遍性的框架”。因此加强复杂网络基础理论和应用研究具有紧迫的重要意义。

回忆20世纪相对论与几何学、量子力学与泛函分析的美好联姻，新世纪会不会有一段复杂网络(统计力学)与马氏过程的浪漫爱情？如果有，那将成为科学史上的佳话。

[1] WATTS D J, STROGATZ S H. Collective dynamics of small-world networks[J]. Nature, 1998, 393: 440-442.

[2] BARABÁSI A-L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286: 509-512.

[3] KLEINBERG J M. Navigation in a small world[J]. Nature,2000, 406: 845.

[4] ALBERT R, JEONG H, BARABÁSI A-L. Diameter of the world-wide web[J]. Nature, 1999, 401: 130-131.

[5] JEONG H, TOMBOR B, ALBERT R, et al. The large-scale organization of metabolic networks[J]. Nature, 2000, 407:651-654.

[6] RAVASZ E, SOMERA A L, MONGRU D A, et al.Hierarchical organization of modularity in metabolic networks[J]. Science, 2002, 297: 1551-1555.

[7] ALBERT R, JEONG H, BARABÁSI A-L. Error and attack tolerance of complex networks[J]. Nature, 2000, 406:378-382.

[8] BARABÁSI A-L. Scale-free networks: A decade and beyond[J]. Science, 2009, 325: 412-413.

[9] BOLLOBÁS B, RIORDAN O M, SPENCER J, et al. The degree sequence of a scale-free random graph process[J].Random Structures and Algorithms, 2001, 18: 279-290.

[10] DOROGOVTSEV S N, MENDES J F F, SAMUKHIN A N.Structure of growth networks with preferential linking[J].PRL, 2000, 85: 4633-4636.

[11] HOLME P, KIM B J. Growing scale-free networks with tunable clustering[J]. PRE, 2002, 65: 026107.

[12] LI L, ALDERSON D, DOYLE J C, et al. Towards a theory of scale-free graphs: definitions, properties, and implications[J]. Internet Math, 2005, 2: 431-523.

[13] DOYLE J C, ALDERSON D, LI L, et al. The “robust yet fragile” nature of the Internet[J]. PNAS USA, 2005, 102:14497-14502.

[14] SHI D H, ZHOU H J, LIU L M. A discussion of Barabási and Albert’s 1999 paper[J]. Physics Procedia 2010, 3:1767-1774.

[15] KRAPIVSKY P L, REDNER S. Network growth by coping[J]. PRE, 2005, 71: 036118.

[16] KRAPIVSKY P L, REDNER S. Finiteness and fluctuations in growing networks[J]. Physica A: Math Gen, 2002, 35:9517-9534.

[17] HONG H, HA M, PARK H. Finite-size scaling in complex networks[J]. PRL, 2007, 98: 258701.

[18] CASTELLANO C, PASTOR-SATORRAS R. Routes to thermodynamic limit on scale-free networks[J]. PRL, 2008,100: 148701.

[19] BRODER A, KUMAR R, MAGHOUL F, et al. Graph structure in the web[J]. Computer Networks, 2000, 33:309-320.

[20] ZHANG G Q, ZHANG G Q, YAN Q F, et al. Evolution of the Internet and its cores[J]. New J Phys, 2008, 10: 123027.[21] BARABÁSI A-L, RAVASZ E, VICSEK T. Determinic scale-free networks[J]. Physica A, 2001, 229: 559-564.

[22] FARKAS I, DERÉNYI I, JEONG H, et al. Networks in life:scaling properties and eigenvalue spectra[J]. Physica A,2002, 314: 25-34.

[23] RAVASZ E, BARABÁSI A-L. Hierarchical organization in complex networks[J]. PRE, 2003, 67: 026112.

[24] DOROGOVTSEV S N, GOTSEV A V, MENDES J F F.Pseudofractal scale-free web[J]. PRE, 2002, 65: 066122.

[25] ANDRADE J S, HERRMANN H J, ANDRADE R F S, et al. Apollonian networks[J]. PRL, 2005, 94: 018702.

[26] ANDRADE J S, HERRMANN H J, ANDRADE R F S, et al. Erratum: Apollonian networks[J]. PRL, 2009, 102:079901.

[27] TANAKA R. Scale-rich metabolic networks[J]. PRL, 2005,94: 168101.

[28] BOLLOBÁS B, RIORDAN O. Robustness and vulnerability of scale-free random graphs[J]. Internet Math,2004, 1: 1-35.

[29] PASTOR-SATORRAS R, VESPIGNANI A. Epidemic spreading in scale-free networks[J]. PRL, 2001, 86: 3200-3203.

[30] MÓRI T. F. The maximum degree of the Barabási random tree[J]. Combinatorics, Probability and Computing, 2005,14: 339-348.

[31] 周晖杰, 叶 臣, 阎春宁, 等. BA模型网络最大度的发散和扰动[C]// 数学·力学·物理学·高新技术交叉研究进展. 北京: 科学出版社, 2010, 13: 232-237.ZHOU H J, YE C, YAN C N, et al. Divergence form and fluctuation law of the maximum degree in the BA model[C]// The progress of interdisciplinary research for mathematics, physics and high new technology[M]. Beijing:Science Press. Beijing: Science Press, 2010, 13: 232-237.

[32] NEWMAN M E J. Assortative mixing in networks[J]. PRL,2002, 89: 208701.

[33] 史定华, 周晖杰. 一种新的度相关测度[C]//第六届全国复杂网络学术会议. 苏州: 中国工业与应用数学学会复杂系统与复杂网络专业委员会, 2010.SHI D H, ZHOU H J. A new measurement for degree correlation[C]//The 6thChinese Conference of Complex Networks. Suzhou: China Society of Industrial and Applied Mathematics, Complex Systems and Complex Networks Technical Committee, 2010.

[34] KRAPIVSKY P L, REDNER S. Organization of growing random networks[J]. PRE, 2001, 63: 066123.

[35] BRIN S, PAGE L. The anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks and ISDN Systems, 1998, 30: 107-117.

[36] KLEINBERG J M. Authoritative sources in a hyperlinked environment[J]. J ACM, 1999, 46: 604-632.

[37] LIU Y T, GAO B, LIU T Y, et al. BrowseRank: letting web users vote for page importance[C]//Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, Singapore, ACM NY USA, 2008: 451-458.

[38] KRAPIVSKY P L, REDNER S, LEYVRAZ F.Connectivity of growing random networks[J]. PRL, 2000,85: 4629-4632

[39] COOPER C, FRIEZE A. A general model of Web graphs[J].Random Structures and Algorithms, 2003, 22: 311-335.

[40] SHI D H, CHEN Q H, LIU L M. Markov chain-based numerical method for degree distributions of growing networks[J]. PRE, 2005, 71: 036140.

[41] HOU Z T, KONG X X, SHI D H, et al. Degree-distribution stability of scale-free networks[J]. arXiv: 0805.1434v1[math.PR] 9 May 2008

[42] XU H, SHI D H. Stability of the BA network: a new approach to rigorous proof[J]. CPL, 2009, 26: 038901-4.

[43] SHI D H, XU H, LIU L M. A vertex-number-evolving markov chain of networks[J]. Physics Procedia 2010, 3,1757-1765.

[44] ZHOU J. (Ed.). Complex sciences——lecture notes of the institute for computer sciences, social informactics and telecommunications engineering[M]. [S.l.]: Springer, 2009:1827-1837.

[45] SHI D H, ZHOU H J, LIU L M. Markovian iterative method for degree distributions of growing networks[J].PRE, 2010, 82: 031105.