第15章 网络科学

小世界

我住在俄勒冈州波特兰，这个市区大约有200万人。我在波特兰州立大学（Portland State University, PSU）任教，学校有将近25000名学生，超过1200名教师。几年前，我们家换了新房子，离学校较远。有一次我同我们的新邻居桃乐茜聊天，她是位律师。我告诉她我在波特兰州立大学教书。她说：“不知道你认不认识我父亲。他叫乔治·勒恩达理斯（George Lendaris）。”我很吃惊。勒恩达理斯是我在PSU的同事，整个学校只有三四个老师研究人工智能，其中就包括我们俩。就在前天，我还和他见了面，讨论合作申请经费。这世界真小！

几乎所有人都有过这种“小世界”经历，很多比我遇到的更具戏剧性。我丈夫高中最好的朋友和我在人工智能课上采用的课本的作者是堂兄弟。在圣塔菲住在离我三栋房子里的一位女士是我在洛杉矶的高中英语老师的好友。我相信你也有过类似的经历。

这种出人意料的关系到底有多常见呢？20世纪50年代，哈佛大学的心理学家米尔格兰姆（Stanley Milgram，图15.1）对这个问题产生了兴趣，他想弄清在美国一个人平均要通过几个熟人关系才能到达另一个人。他设计了一个实验，实验中一些普通人被要求将一封信寄给一位陌生人，他可以将信交给他认为最有可能将信送达的熟人，熟人又转交给熟人的熟人，直到信通过熟人关系形成的链条送到收信人手中。

米尔格兰姆在报纸上刊登广告，在堪萨斯州和内布拉斯加州招募了一群“发信人”，告诉他们“收信人”的姓名、职位和所在城市，发信人要把信送给他不认识的这位收信人。米尔格兰姆选择的收信人中，有一个例子是波士顿的一位股票经纪人，还有一个例子是坎布里奇（Cambridge）附近一位神学学生的妻子。发信人被要求将信送给他认识的某位熟人，再请这位熟人继续传送。传送过程被记录在信上，如果信送到了收信人手里，米尔格兰姆就计算信经过了几个熟人关系。米尔格兰姆记述了一个例子：

在信封被交给堪萨斯州一位发信人4天后，圣公会神学院的一位教师在街上拦住了我们的收信人。他将一个牛皮信封塞给她：“爱丽丝，这是你的。”一开始她以为这是一封没有送到发信人手里被退回来的信，从没有离开过坎布里奇，但是当我们看上面的记录时，我们惊喜地发现信是堪萨斯州的一位农夫寄来的。他将信交给了他们当地圣公会的牧师，这位牧师又将信寄给了在坎布里奇任教的这位牧师，这位牧师再将信交给了收信人。这样从发信人经过两个熟人关系就到了收信人！

在这项著名的实验中，米尔格兰姆发现，在送达的信件中，从发信人平均经过5个熟人就送到了收信人的手中。这个发现后来广为人知，被称为“六度分隔（six degrees of separation）”。

后来心理学家柯兰菲尔德（Judith Kleinfeld）研究发现，米尔格兰姆的发现被曲解了——事实上，大部分信件从没有到达收信人手中，而在米尔格兰姆的其他研究中，到达收信人的信件经过的平均熟人关系也不止5个。然而，六度分隔的小世界思想还是成了我们文化的传奇。正如柯兰菲尔德指出的：

当人们发现出人意料的社会关系时，很有可能会印象深刻……在理解自然界的巧合时，我们的数学水平不高，直觉也不咋样。

那这到底是不是一个小世界呢？这个问题最近又受到很多关注，不仅仅是社会网络，还涉及其他各种网络，包括活细胞中的代谢网络和遗传调节网络，以及增长迅猛的万维网。过去十年中，这些网络的问题吸引了无数复杂系统研究者，从而产生了所谓的“网络新科学”。

网络新科学

你肯定看到过类似于图15.2这样的网络图。这是大陆航空（Continental Airlines）在美国的航线图。点（或节点）代表城市，线（或连接）代表城市之间的航班。

许多自然、技术和文化现象经常被描述为网络，航线图就是一个明显的例子。大脑是神经元通过突触连接起来的巨大网络。细胞中的遗传活动是受由基因通过调节蛋白质连接起来的复杂网络控制。社会则是由各种各样的关系连接起来的人（或组织）组成的网络。万维网则更是现代社会的典型网络。在国家安全领域，识别和分析可能的“恐怖分子网络”是很重要的工作。直到不久前，网络科学都不被视为一个研究领域。数学家研究抽象网络结构的学科被称为“图论”，神经科学家研究神经网络，流行病学家研究疾病通过人际网络的传播。像米尔格兰姆这样的社会学家和社会心理学家则研究社会网络的结构。经济学家研究经济网络的行为，例如技术革新在商业网络中的传播。航空公司主管则研究图15.2这样的网络，想找到在一定条件下能获得更多利润的网络结构。他们基本上都是各干各的，通常都互相不知道其他人的工作。

不过，近十年来，越来越多的应用数学家和物理学家开始着迷于研究一系列操控所有自然、社会和技术网络的普适原理。这股网络研究浪潮是由20世纪90年代末的两篇重要文章引发的：邓肯·瓦特（Duncan Watts，图15.3）和斯托加茨（Steven Strogatz，图15.4）的《‘小世界网络’的集体动力学》，以及巴拉巴西（Albert-László Barabási，图15.5）和艾伯特（Réka Albert）的《随机网络中标度的涌现》。这两篇文章分别发表在世界上最著名的科学期刊《自然》和《科学》上，很快就引起了巨大反响。关于网络的各种新发现迅速涌现。

网络科学的兴起恰逢其时。对各种网络的共性的研究，无论是仿真还是统计大量真实数据，都只有在计算机的速度足够快之后才可能做到。在20世纪90年代，条件成熟了。不仅如此，随着万维网在社会、商业和科学网络中越来越普及，大量数据都能很容易地得到。

此外，许多非常聪明的物理学家已经厌倦了越来越抽象的现代物理学，想要研究点别的东西。网络既包含数学和复杂系统动力学，又与现实世界相关，因此成为理想的研究对象。就像邓肯·瓦特说的（他自己是应用数学家和社会学家），“一大群饥肠辘辘的物理学家兴奋地循着新问题的香味涌来”。

这些聪明人掌握了合适的数学工具，能够将复杂问题简单化，同时又不丢掉本质特征。一些从物理学家转型而来的网络科学家已经成为这个领域的领导者。

也许最重要的是，这些科学家逐渐意识到，各种高度复杂的网络系统对人类生活和福祉的影响越来越大，迫切需要有新的思想和方法——真正全新的思考方式——来帮助理解它们。

巴拉巴西将这种新方法称为“网络思维”，并认为“网络思维将渗透到人类活动和人类思想的一切领域”。

什么是网络思维

网络思维意味着关注的不是事物本身，而是事物之间的关系。例如，第7章曾讲过，人类和芥菜都大致有25000个基因，这似乎无法体现人类与这种植物的生物复杂性的差别。近几十年来，一些生物学家提出生物的复杂性主要来自基因之间交互作用的复杂性。在第18章我们会详细讨论这一点，现在知道网络思维的最新成果对生物学有深刻影响就够了。

最近，网络思维还帮助厘清了一些看似无关的科学和技术之谜：为什么生物的生命期与它们的大小基本上遵循一个简单的函数？为什么谣言和笑话传播得如此之快？为什么电网和万维网这样大规模的复杂网络有时候非常稳健，有时候却又容易出现大范围崩溃？什么样的事件会让本来很稳定的生态群落崩溃？

这些问题看似毫不相干，网络科学家却认为答案反映了各种网络的共性。网络科学的目的就是提炼出这些共性，并以它们为基础，用共同的语言来刻画各种不同的网络。同时网络科学家也希望能理解自然界中的网络是如何发展而来的，以及它们是如何随时间变化的。对网络的科学理解不仅会改变我们对各种自然和社会系统的理解，同时也会帮助我们更好地规划和更有效地利用复杂网络，包括更好的网络搜索和万维网路由算法，控制疾病传播和有组织犯罪，以及保护生态环境。

到底什么是“网络”

要科学地研究网络，我们必须精确地定义网络的意义。用最简单的话说，网络是由边连接在一起的节点组成的集合。节点对应网络中的个体（例如神经元、网站、人），边则是个体之间的关联（例如突触、网页超链接、社会关系）。

图15.6展示了一部分我自己的社会网络——一些我最密切的朋友以及他们的一些最密切的朋友，总共19个节点。（当然大部分“真实的”网络比这个要大得多。）初看上去，这个网络就像一团乱麻。然而，如果你仔细看一下，就会在这一团乱麻中发现一些结构。有一些联系紧密的群体——这不奇怪，我的一些朋友相互之间也是朋友。例如，David、Greg、Doug和Bob相互连接，Steph、Ginger和Doyne也是这样，我自己则是这两个群体之间的桥梁。不了解我的历史的人可能也猜得出这两个朋友“群体”与我的不同兴趣或不同的人生阶段有关。（两个答案都正确。）

你可能还注意到一些人有很多朋友（例如我自己、Doyne、David、Doug、Greg），一些人则只有一个朋友（例如Kim、Jacques、Xiao）。这是因为这个网络不完整，但是在大型社会网络中，总是有一些人有许多朋友，有一些人则朋友较少。

网络科学家创造了一些术语来描述各种类型的网络结构。网络中存在的内部联系紧密、外部较松散的群体被称为集群（clustering）。进出一个节点的边的数量称为这个节点的度（degree）。例如，我的度就是10，是所有节点中最高的。Kim的度为1，与其他5个人一起是最低的。借助这些术语，我们可以说网络中有少数高连接度的节点，以及大量低连接度的节点。

在图15.7的网络度分布中，这一点可以看得很清楚。横坐标为度，长条的高度则对应具有这个度的节点的数量。例如，有6个节点的度为1（第一个长条），有1个节点的度为10（最后一个长条）。

从图中可以清楚看到大量节点具有低连接度，少量节点具有高连接度。在社会网络中，这表明大部分人的朋友相对较少，极少的人具有很多很多朋友。类似的，在万维网上，少数网站极受欢迎（很多网站都有链接指向这些网站），例如有超过7500万个链接指向谷歌，而大部分网站则几乎没什么知名度——例如只有123个链接指向我自己的网站（其中大部分可能都来自搜索引擎）。

高连接度的节点被称为中心节点（hub），它们是网络中主要的信息或行为的传递渠道。图15.2显示了大多数航空公司在20世纪80年代解除管制后采用的中心节点系统：各家航空公司都选择特定的一些城市作为中心节点，大部分航班都经过这些城市。如果你曾坐大陆航空的航班从美国西部飞到东海岸去，你可能就会在休斯敦转机。

网络科学家发现，他们研究过的自然、社会和技术网络中，大部分都具有这些特征：高度的集群性、不均衡的度分布以及中心节点结构。这些特征的出现显然不是偶然的。如果我将节点随机连接起来生成一个网络，则所有节点的度数都会差不多，得到的度分布就不会像图15.7那样。同样的，网络中也不会有中心节点和小的集群。

为什么现实世界中的网络会具有这些特征呢？这是网络科学的主要问题，目前基本上已经通过建立网络的发展模型解决了。其中有两类模型被深入地进行了研究，分别是小世界网络（small—world networks）和无尺度网络（scale—free networks）。

小世界网络

米尔格兰姆的实验也许不能证明我们的社会是一个小世界，但我的社会网络（图15.6）的确是个小世界。从一个节点出发，用不了几步就能到达其他任何节点。Gar只需3步就能到达Charlie, John只需4步就能到达Xiao，虽然他们从未谋面（据我所知是这样）。在我的网络中人们最多相隔4度。

应用数学家和社会学家邓肯·瓦特与应用数学家斯托加茨率先从数学上定义了小世界网络的概念，并且研究了怎样的网络结构会具有这种特性。（他们对网络的抽象研究的灵感来源出人意料：来自对蟋蟀如何同步鸣叫的研究。）瓦特和斯托加茨从一个最简单的“规则”网络开始：由60个节点组成的一个环，如图15.8所示。每个节点与相邻的两个节点相连，像一个初等的元胞自动机。为了确定网络的“小世界”程度，瓦特和斯托加茨计算了网络的平均路径长度。两个节点之间的路径长度就是两个节点之间最短路径的边的数量。平均路径长度则是网络中所有节点对之间的路径长度的平均值。结果图15.8中的规则网络的平均路径长度为151。如果玩传话游戏，要与坐在对面的人沟通会需要很长时间。

瓦特和斯托加茨想知道，如果我们对这样的规则网络稍加改动，将少量与相邻节点连接的边改成长距离连接，平均路径长度会受到怎样的影响呢？他们发现，影响相当剧烈。

图15.9是对图15.8网络中5%的边（3条）进行重连后得到的网络，重连时3条边的一端被解开，重新连接到一个随机选择的节点上。

重连后的网络与原来的规则网络的边数量一样多，但是平均路径长度一下就降到了9左右。瓦特和斯托加茨发现，节点数量越多，这个效应越明显。例如，如果是有1000个节点的规则网络，平均路径长度是250，如果5%的边重连，平均路径长度会一下降到20。瓦特说：“只需很少的随机连接就能产生很大的效应……不管网络的规模多大，前5个随机重连会将平均路径长度平均减少一半。”

这解释了小世界性：一个网络如果只有少量的长程连接，相对于节点数量来说平均路径却很短，则为小世界网络。小世界网络也经常表现出高度的集群性：任选3个节点A、B、C，如果节点A与节点B和C相连，则B与C也很有可能相连。这在图15.9中不明显，因为这个网络中大部分节点都只与两个相邻节点相连。但如果网络更贴近真实，也就是说节点与更多节点相连，则集群性会很高。我自己的社会网络就是一个例子——我的朋友的朋友也很有可能是我的朋友。

瓦特和斯托加茨还研究了3个真实世界中的网络，结果表明它们都具有小世界性。一个是电影演员网络。在这个网络中，节点代表演员；如果两个演员出现在同一部电影中，例如汤姆·克鲁斯和马克斯·冯·赛多（《少数派报告》，Minority Report），卡梅隆·迪亚兹和朱莉娅·罗伯茨（《我最好朋友的婚礼》，My Best Friend's Wedding），则相应的两个节点就相互连接。这个网络因著名的“凯文·贝肯游戏”（Kevin Bacon game）而受到关注，游戏参与者尝试在网络中寻找任意一位电影演员与多产的电影明星凯文·贝肯的最短路径。一般来说，如果你是演电影的，与凯文·贝肯之间的路径很长，就说明你在演艺界混得不好。

第二个例子是美国西部电网。网络中的节点代表电网的主要组成部分：电厂、变压器、变电站。边代表它们之间的高压输电线。第三个例子是线虫的神经网络，节点代表神经元，边则代表神经元之间的连接。（瓦特和斯托加茨很幸运，神经学家已经绘制出了这种低等生物的所有神经元和连接。）

很难想象电影明星与电力系统之间存在共性，更不要说线虫的脑神经，但瓦特和斯托加茨的研究表明它们实际上都是小世界网络，平均路径很短，具有高度的集群性。

瓦特和斯托加茨1990年发表的著名文章——《“小世界网络”的集体动力学》——引发了网络科学的研究浪潮。科学家们在现实世界中发现了越来越多的小世界网络，在下一章我们将介绍其中一部分。自然、社会和技术演化产生的许多生物、群体和产品似乎都具有这种结构。这是为什么呢？有假说认为至少有两种相互矛盾的选择压力导致了这种结果：在系统内快速传播信息的需要，以及产生和维持可靠的远程连接的高成本。小世界网络具有较短的平均路径长度，同时又只需相对较少的长程连接，从而解决了这两个问题。

进一步的研究表明，根据瓦特和斯托加茨提出的方法——从规则网络开始，对一小部分边进行随机重连——产生的网络与许多真实世界网络的度分布并不一样。很快不同的网络模型就被提了出来，其中就包括无尺度网络——一种更类似现实世界网络的小世界网络。

无尺度网络

你肯定搜索过万维网，你也很有可能将谷歌作为你的搜索引擎。（如果你读这本书的时间离我写书的2008年已经过去了很久，流行的也许是新的搜索引擎。）在谷歌出现之前，搜索引擎的做法是在一张索引上搜索你查询的单词，索引将所有可能的英文单词对应到包含有这个单词的网页的列表。比如，如果你用“apple（苹果）records（唱片、记录）”这两个单词进行搜索，搜索引擎会列出包含这两个单词的所有网页，根据这些单词的出现次数进行排序。你可能会得到华盛顿州苹果的历史价格网页，或是塔斯马尼亚大苹果赛的最快时间记录，或是甲壳虫乐队1968年的著名唱片的网页。当时在一大堆不相关的网页中寻找你想要的信息是一件让人充满挫折感的事情。

20世纪90年代，谷歌改变了这一切。谷歌提出了一种革命性的思想，用一种称为“网页排名（Page Rank）”的方法对网页搜索结果进行排序。其中的思想是网页的重要性（和可能的相关性）与指向这个网页的链接数量（入连接的数量）有关。例如，在我写下这些的时候，《美国西部果农》报道2008年苹果价格的网页有39个入连接，关于塔斯马尼亚大苹果赛信息的网页有47个入连接。甲壳虫乐队官网（www.beatles.com）有大约27000个入连接。在搜索“apple records”时这个网页位于列表前面。在搜索到的近100万个网页中，另两个网页则远远排在后面。最初的网页排名的思想非常简单，但它极大地改善了搜索引擎，与搜索单词最相关的网页通常都位于列表的前面。

如果我们将万维网看作一个网络，节点是网页，边是网页之间的超链接，我们就能发现网页排名之所以有效是因为这个网络具有特定的结构：同典型的社会网络一样，大部分网页为低连接度（入连接相对较少），极少部分网页具有高连接度（入连接相对较多）。此外，网页之间的入连接数量差别很大，这样才使得排名有意义——能真正对网页进行区分。换句话说，万维网具有前面描述的那种度分布和中心节点结构。而且它也具有高度的集群性——一些网页“群体”内部相互连接。用网络科学的术语说，万维网是无尺度网络。这在最近的复杂系统研究中是最热门的话题，因此我们来稍加深入地了解一下万维网的度分布，以及无尺度到底指的是什么。

万维网的度分布

怎样分析万维网的度分布呢？万维网连接有两种：入连接和出连接。如果我的网页有一个链接指向你的网页，而你却没有指向我，则我有一个出连接而你则有一个入连接。我们必须明确考虑的是哪种连接。最初的网页排名算法只关注入连接而忽略出连接——在我们的讨论中也是一样。我们将网页的入连接数量称为网页的入度（in—degree）。

这样问题就是万维网的入度分布是怎样的？要考虑所有的网页和入连接极为困难——并不存在完整的列表，而且不断有新的连接产生，旧的连接消失。不过一些网络学家还是通过采样和巧妙的网络爬虫（Web—crawling）技术得到了近似结果。对网页总数的估计各种各样；2008年时，我看到的估计从1亿到100亿都有，而且显然网页数量还在迅速增长。

几个研究团体都发现网页入度分布可以用非常简单的规则来描述：具有某一入度的网页数量大致正比于入度的平方的倒数。如果用字母k表示入度。则（在文献中对于k的指数的具体数值有些分歧，但是都接近2——细节见注释）这个规则实际上只适用于注7入度（k）为数千或更大的情形。

注7 “这个规则实际上只适用于”：网页的入度分布基本符合幂律k-2.3，下限kmin=3684[参见Clauset, A.，Shalizi, C.R.，&Newman, M.E.J.，Power-law distributions in empirical data.Preprint，2007（http://arxiv.org/abs/0706.1062）。]为了便于讨论，这一章中将式子简化近似为k-2；k-2.3分布的图与这一章给出的图非常相似。

入度为k的网页数量正比于1/k2。

为了解释为何万维网是“无尺度”，我用三种不同的尺度画出了遵循上面的规则的入度分布（图15.10）。第一幅图画了9000个入度对应的分布，从1000开始，这是规则开始变得相当精确的地方。类似于图15.7，横轴为1000—10000的入度值，纵轴标示的长条高度则是各入度值的频率（具有相应入度的网页数量）。长条太多以至于形成了一整块黑色区域。

图中给出的并不是频率的真实值，因为我想强调图形的形状（据我所知，也没有人对实际频率有很好的估计）。图中可以看到入度k为1000的网页相对较多，随着入度增大，频率下降很快。在k=5000和k=10000之间，网页数量已经很少了，对应的长条高度已基本接近0。

如果我们改变尺度，将这片“基本接近0”的区域放大，会怎么样呢？第二幅图绘制了k=10000到k=100000之间的入度分布。我改变了图形的尺度，让k=10000处与前一幅图中k=1000处的长条高度相等。在这个尺度下，入度为k=10000的网页数量相对较多，在k=50000和k=100000之间的长条高度则“基本接近0”。

但还有一点很惊人——除了坐标轴上的数字不同，第二幅图与第一幅图是一样的。第一幅图画了9000个值的分布，而第二幅图画了90000个值的分布，足足大了一个数量级。

第三幅图中可以看到在更大的尺度上仍然有相同的现象。k为100000到1000000之间，画出的分布形状仍然是一样的。

这样的分布被称为是自相似的，因为不管在哪种尺度上进行绘制，形状都是一样的。说得更专业一点，就是“在不同尺度下具有不变性”。这就是无尺度一词的由来。自相似这个词可能会让你觉得似曾相识。因为在第7章讨论分形时我们见过它。这里与分形确实有一些联系，到第17章我们再来详细讨论。

无尺度分布和钟形曲线

无尺度网络没有“特征尺度”。要解释这一点，最好的办法是将无尺度分布与另一种著名的分布——钟形曲线——进行比较。

假设我们绘制全世界成年人身高的分布。世界上最矮的（成年）人大约是70厘米，最高的人则大约是270厘米。成年人的平均身高大约是165厘米，而且大部分人的身高介于150—200厘米之间。人类身高分布大致像图15.11那样。画出来的曲线像一座钟，钟形曲线也因此而得名。很多东西的分布都接近钟形曲线——身高、体重、考试成绩、篮球赛得分、各种物种的数量，等等。自然界中有许多量都遵循这种分布，因此钟形曲线也被称为正态分布。正态分布有特定的尺度——比如，身高是70—270厘米，考试成绩是0—100分。在正态分布中，平均值同时也是频率最高的值，例如165厘米既是身高平均值也是最常见的值。大部分取值与平均值相差不大——分布相当单一。如果网页的入度值是正态分布，网页排名就不会起作用，因为几乎所有网页的入连接都差不多。甲壳虫乐队的官网与其他包含“apple records”的网页的入连接数量就会相差不大，因而无法用来区分可能的相关程度。

幸运的是（对谷歌的股东来说尤其如此），网页的度分布是无尺度而不是钟形曲线。无尺度网络有4个显著特征：①相对较少的节点具有很高的度（中心节点）；②节点连接度的取值范围很大（度的取值多样）；③自相似性；④小世界结构。所有的无尺度网络同时也具有小世界特性，但不是所有具有小世界特性的网络都是无尺度网络。

说得专业一点，无尺度网络一定遵循连接度幂律分布。前面已经讲了，网页的入度分布大致是：

入度为k的网页数量正比于1/k2。

你可能还记得高中数学学过1/k2也可以写成k-2。即“指数为-2的幂律分布”。类似的，1/k即（k-1）就是“指数为-1的幂律分布”。幂律分布的形式一般为xd，其中x是入度这一类的量。描述这种分布的关键是指数d；不同的指数会产生不同的分布。

在第17章我们再深入讨论幂律分布。现在只需记住无尺度网络遵循连接度幂律分布。

网络稳健性

无尺度网络有一个非常重要的特性，在节点被删除时具有稳健性。也就是说，如果随机删除一些节点，不会改变网络的基本特性：仍然会有多样的度分布、很短的平均路径以及很高的集群性，即使删除的节点很多也不会有什么变化。原因很简单：如果随机删除节点，则极有可能删除的是低连接度的节点，因为网络中绝大部分节点都是低连接度节点。删除这种节点对总体的度分布和路径长度的影响很小。万维网就是这样，网络上不断有计算机出故障或是被移除，但是这对万维网的运转不会有明显影响，也不会改变其平均路径长度。类似的，网页和链接也在不断被删除，但网上冲浪不会受到什么影响。

不过，这种稳健性是有代价的：如果删除了中心节点，网络就有可能会失去无尺度特性，并且无法正常运转。例如，芝加哥（航班网络的中心节点）的暴风雪可能会导致全国大面积的航班延误或取消。谷歌出故障会对整个万维网形成很大冲击。

总而言之，无尺度网络对节点的随机删除具有稳健性，但如果中心节点失效或是受到攻击就会非常脆弱。

下一章我们将讨论几个具有小世界和无尺度特性的真实网络，以及一些对它们的形成进行解释的理论。