1701067830
1701067831
1701067832
▲图15.6 一部分我自己的社会网络
1701067833
1701067834
在图15.7的网络度分布中，这一点可以看得很清楚。横坐标为度，长条的高度则对应具有这个度的节点的数量。例如，有6个节点的度为1（第一个长条），有1个节点的度为10（最后一个长条）。
1701067835
1701067836
从图中可以清楚看到大量节点具有低连接度，少量节点具有高连接度。在社会网络中，这表明大部分人的朋友相对较少，极少的人具有很多很多朋友。类似的，在万维网上，少数网站极受欢迎（很多网站都有链接指向这些网站），例如有超过7500万个链接指向谷歌，而大部分网站则几乎没什么知名度——例如只有123个链接指向我自己的网站 [228] （其中大部分可能都来自搜索引擎）。
1701067837
1701067838
1701067839
1701067840
1701067841
▲图15.7 图15.6中的网络的度分布。图中的长条代表具有相应度数的节点的数量
1701067842
1701067843
高连接度的节点被称为中心节点（hub），它们是网络中主要的信息或行为的传递渠道。图15.2显示了大多数航空公司在20世纪80年代解除管制后采用的中心节点系统：各家航空公司都选择特定的一些城市作为中心节点，大部分航班都经过这些城市。如果你曾坐大陆航空的航班从美国西部飞到东海岸去，你可能就会在休斯敦转机。
1701067844
1701067845
网络科学家发现，他们研究过的自然、社会和技术网络中，大部分都具有这些特征：高度的集群性、不均衡的度分布以及中心节点结构。这些特征的出现显然不是偶然的。如果我将节点随机连接起来生成一个网络，则所有节点的度数都会差不多，得到的度分布就不会像图15.7那样。同样的，网络中也不会有中心节点和小的集群。
1701067846
1701067847
为什么现实世界中的网络会具有这些特征呢？这是网络科学的主要问题，目前基本上已经通过建立网络的发展模型解决了。其中有两类模型被深入地进行了研究，分别是小世界网络（small—world networks）和无尺度网络（scale—free networks）。
1701067848
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