1701067849
复杂 [:1701064815]
1701067850
小世界网络
1701067851
1701067852
米尔格兰姆的实验也许不能证明我们的社会是一个小世界，但我的社会网络（图15.6）的确是个小世界。从一个节点出发，用不了几步就能到达其他任何节点。Gar只需3步就能到达Charlie, John只需4步就能到达Xiao，虽然他们从未谋面（据我所知是这样）。在我的网络中人们最多相隔4度。
1701067853
1701067854
应用数学家和社会学家邓肯·瓦特与应用数学家斯托加茨率先从数学上定义了小世界网络的概念 [229] ，并且研究了怎样的网络结构会具有这种特性。（他们对网络的抽象研究的灵感来源出人意料：来自对蟋蟀如何同步鸣叫的研究。）瓦特和斯托加茨从一个最简单的“规则”网络开始：由60个节点组成的一个环，如图15.8所示。每个节点与相邻的两个节点相连，像一个初等的元胞自动机。为了确定网络的“小世界”程度，瓦特和斯托加茨计算了网络的平均路径长度。两个节点之间的路径长度就是两个节点之间最短路径的边的数量。平均路径长度则是网络中所有节点对之间的路径长度的平均值。结果图15.8中的规则网络的平均路径长度为15 1 。如果玩传话游戏，要与坐在对面的人沟通会需要很长时间。
1701067855
1701067856
1701067857
1701067858
1701067859
▲图15.8规则网络的例子。这个网络是由节点组成的一个环，每个节点都与相邻的两个节点相连
1701067860
1701067861
瓦特和斯托加茨想知道，如果我们对这样的规则网络稍加改动，将少量与相邻节点连接的边改成长距离连接，平均路径长度会受到怎样的影响呢？他们发现，影响相当剧烈。
1701067862
1701067863
图15.9是对图15.8网络中5%的边（3条）进行重连后得到的网络，重连时3条边的一端被解开，重新连接到一个随机选择的节点上。
1701067864
1701067865
1701067866
1701067867
1701067868
▲图15.9 将3条边随机重连，使得图15.8的规则网络变成了小世界网络
1701067869
1701067870
重连后的网络与原来的规则网络的边数量一样多，但是平均路径长度一下就降到了9左右 [230] 。瓦特和斯托加茨发现，节点数量越多，这个效应越明显。例如，如果是有1000个节点的规则网络，平均路径长度是250，如果5%的边重连，平均路径长度会一下降到20。瓦特说：“只需很少的随机连接就能产生很大的效应 [231] ……不管网络的规模多大，前5个随机重连会将平均路径长度平均减少一半。”
1701067871
1701067872
这解释了小世界性 [232] ：一个网络如果只有少量的长程连接，相对于节点数量来说平均路径却很短，则为小世界网络。小世界网络也经常表现出高度的集群性：任选3个节点A、B、C，如果节点A与节点B和C相连，则B与C也很有可能相连。这在图15.9中不明显，因为这个网络中大部分节点都只与两个相邻节点相连。但如果网络更贴近真实，也就是说节点与更多节点相连，则集群性会很高。我自己的社会网络就是一个例子——我的朋友的朋友也很有可能是我的朋友。
1701067873
1701067874
瓦特和斯托加茨还研究了3个真实世界中的网络，结果表明它们都具有小世界性。一个是电影演员网络。在这个网络中，节点代表演员；如果两个演员出现在同一部电影中，例如汤姆·克鲁斯和马克斯·冯·赛多（《少数派报告》，Minority Report），卡梅隆·迪亚兹和朱莉娅·罗伯茨（《我最好朋友的婚礼》，My Best Friend’s Wedding），则相应的两个节点就相互连接。这个网络因著名的“凯文·贝肯游戏” [233] （Kevin Bacon game）而受到关注，游戏参与者尝试在网络中寻找任意一位电影演员与多产的电影明星凯文·贝肯的最短路径。一般来说，如果你是演电影的，与凯文·贝肯之间的路径很长，就说明你在演艺界混得不好。
1701067875
1701067876
第二个例子是美国西部电网。网络中的节点代表电网的主要组成部分：电厂、变压器、变电站。边代表它们之间的高压输电线。第三个例子是线虫的神经网络，节点代表神经元，边则代表神经元之间的连接。（瓦特和斯托加茨很幸运，神经学家已经绘制出了这种低等生物的所有神经元和连接。 [234] ）
1701067877
1701067878
很难想象电影明星与电力系统之间存在共性，更不要说线虫的脑神经，但瓦特和斯托加茨的研究表明它们实际上都是小世界网络，平均路径很短，具有高度的集群性。
1701067879
1701067880
瓦特和斯托加茨1990年发表的著名文章——《“小世界网络”的集体动力学》——引发了网络科学的研究浪潮。科学家们在现实世界中发现了越来越多的小世界网络，在下一章我们将介绍其中一部分。自然、社会和技术演化产生的许多生物、群体和产品似乎都具有这种结构。这是为什么呢？有假说认为至少有两种相互矛盾的选择压力导致了这种结果：在系统内快速传播信息的需要，以及产生和维持可靠的远程连接的高成本。小世界网络具有较短的平均路径长度，同时又只需相对较少的长程连接，从而解决了这两个问题。
1701067881
1701067882
进一步的研究表明，根据瓦特和斯托加茨提出的方法——从规则网络开始，对一小部分边进行随机重连——产生的网络与许多真实世界网络的度分布并不一样 [235] 。很快不同的网络模型就被提了出来，其中就包括无尺度网络——一种更类似现实世界网络的小世界网络。
1701067883
1701067884
复杂 [:1701064816]
1701067885
无尺度网络
1701067886
1701067887
你肯定搜索过万维网，你也很有可能将谷歌作为你的搜索引擎。（如果你读这本书的时间离我写书的2008年已经过去了很久，流行的也许是新的搜索引擎。）在谷歌出现之前，搜索引擎的做法是在一张索引上搜索你查询的单词，索引将所有可能的英文单词对应到包含有这个单词的网页的列表。比如，如果你用“apple（苹果）records（唱片、记录）”这两个单词进行搜索，搜索引擎会列出包含这两个单词的所有网页，根据这些单词的出现次数进行排序。你可能会得到华盛顿州苹果的历史价格网页，或是塔斯马尼亚大苹果赛的最快时间记录，或是甲壳虫乐队1968年的著名唱片的网页。当时在一大堆不相关的网页中寻找你想要的信息是一件让人充满挫折感的事情。
1701067888
1701067889
20世纪90年代，谷歌改变了这一切。谷歌提出了一种革命性的思想，用一种称为“网页排名（Page Rank）”的方法对网页搜索结果进行排序。其中的思想是网页的重要性（和可能的相关性）与指向这个网页的链接数量（入连接的数量）有关。例如，在我写下这些的时候，《美国西部果农》报道2008年苹果价格的网页 [236] 有39个入连接，关于塔斯马尼亚大苹果赛信息的网页 [237] 有47个入连接。甲壳虫乐队官网（www.beatles.com）有大约27000个入连接。在搜索“apple records”时这个网页位于列表前面。在搜索到的近100万个网页中，另两个网页则远远排在后面。最初的网页排名的思想非常简单，但它极大地改善了搜索引擎，与搜索单词最相关的网页通常都位于列表的前面。
1701067890
1701067891
如果我们将万维网看作一个网络，节点是网页，边是网页之间的超链接，我们就能发现网页排名之所以有效是因为这个网络具有特定的结构：同典型的社会网络一样，大部分网页为低连接度（入连接相对较少），极少部分网页具有高连接度（入连接相对较多）。此外，网页之间的入连接数量差别很大，这样才使得排名有意义——能真正对网页进行区分。换句话说，万维网具有前面描述的那种度分布和中心节点结构。而且它也具有高度的集群性——一些网页“群体”内部相互连接。用网络科学的术语说，万维网是无尺度网络。这在最近的复杂系统研究中是最热门的话题，因此我们来稍加深入地了解一下万维网的度分布，以及无尺度到底指的是什么。
1701067892
1701067893
复杂 [:1701064817]
1701067894
万维网的度分布
1701067895
1701067896
怎样分析万维网的度分布呢？万维网连接有两种：入连接和出连接。如果我的网页有一个链接指向你的网页，而你却没有指向我，则我有一个出连接而你则有一个入连接。我们必须明确考虑的是哪种连接。最初的网页排名算法只关注入连接而忽略出连接——在我们的讨论中也是一样。我们将网页的入连接数量称为网页的入度（in—degree）。
1701067897
1701067898
这样问题就是万维网的入度分布是怎样的？要考虑所有的网页和入连接极为困难——并不存在完整的列表，而且不断有新的连接产生，旧的连接消失。不过一些网络学家还是通过采样和巧妙的网络爬虫（Web—crawling）技术得到了近似结果。对网页总数的估计各种各样；2008年时，我看到的估计从1亿到100亿都有，而且显然网页数量还在迅速增长。