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亿都有，而且显然网页数量还在迅速增长。
1701067899
1701067900
几个研究团体都发现网页入度分布可以用非常简单的规则来描述：具有某一入度的网页数量大致正比于入度的平方的倒数。如果用字母k表示入度。则（在文献中对于k的指数的具体数值有些分歧，但是都接近2——细节见注释）这个规则实际上只适用于 [238] 入度（k）为数千或更大的情形。
1701067901
1701067902
入度为k的网页数量正比于1/k 2 。
1701067903
1701067904
为了解释为何万维网是“无尺度”，我用三种不同的尺度画出了遵循上面的规则的入度分布（图15.10）。第一幅图画了9000个入度对应的分布，从1000开始，这是规则开始变得相当精确的地方。类似于图15.7，横轴为1000—10000的入度值，纵轴标示的长条高度则是各入度值的频率（具有相应入度的网页数量）。长条太多以至于形成了一整块黑色区域。
1701067905
1701067906
图中给出的并不是频率的真实值，因为我想强调图形的形状（据我所知，也没有人对实际频率有很好的估计）。图中可以看到入度k为1000的网页相对较多，随着入度增大，频率下降很快。在k=5000和k=10000之间，网页数量已经很少了，对应的长条高度已基本接近0。
1701067907
1701067908
如果我们改变尺度，将这片“基本接近0”的区域放大，会怎么样呢？第二幅图绘制了k=10000到k=100000之间的入度分布。我改变了图形的尺度，让k=10000处与前一幅图中k=1000处的长条高度相等。在这个尺度下，入度为k=10000的网页数量相对较多，在k=50000和k=100000之间的长条高度则“基本接近0”。
1701067909
1701067910
1701067911
1701067912
1701067913
▲图15.10 三种不同尺度下网页入度分布的近似形状
1701067914
1701067915
但还有一点很惊人——除了坐标轴上的数字不同，第二幅图与第一幅图是一样的。第一幅图画了9000个值的分布，而第二幅图画了90000个值的分布，足足大了一个数量级。
1701067916
1701067917
第三幅图中可以看到在更大的尺度上仍然有相同的现象。k为100000到1000000之间，画出的分布形状仍然是一样的。
1701067918
1701067919
这样的分布被称为是自相似的，因为不管在哪种尺度上进行绘制，形状都是一样的。说得更专业一点，就是“在不同尺度下具有不变性”。这就是无尺度一词的由来。自相似这个词可能会让你觉得似曾相识。因为在第7章讨论分形时我们见过它。这里与分形确实有一些联系，到第17章我们再来详细讨论。
1701067920
1701067921
复杂 [:1701064818]
1701067922
无尺度分布和钟形曲线
1701067923
1701067924
无尺度网络没有“特征尺度”。要解释这一点，最好的办法是将无尺度分布与另一种著名的分布——钟形曲线——进行比较。
1701067925
1701067926
假设我们绘制全世界成年人身高的分布。世界上最矮的（成年）人大约是70厘米，最高的人则大约是270厘米。成年人的平均身高大约是165厘米，而且大部分人的身高介于150—200厘米之间。人类身高分布大致像图15.11那样。画出来的曲线像一座钟，钟形曲线也因此而得名。很多东西的分布都接近钟形曲线——身高、体重、考试成绩、篮球赛得分、各种物种的数量，等等。自然界中有许多量都遵循这种分布，因此钟形曲线也被称为正态分布。正态分布有特定的尺度——比如，身高是70—270厘米，考试成绩是0—100分。在正态分布中，平均值同时也是频率最高的值，例如165厘米既是身高平均值也是最常见的值。大部分取值与平均值相差不大——分布相当单一。如果网页的入度值是正态分布，网页排名就不会起作用，因为几乎所有网页的入连接都差不多。甲壳虫乐队的官网与其他包含“apple records”的网页的入连接数量就会相差不大，因而无法用来区分可能的相关程度。
1701067927
1701067928
1701067929