E?G??m?avg_path_length?G?m
这里，m是G中的链路数。极端情况下，E=1.0，每条链路都对链路效率做出了贡献。最差情况下，当E=0，平均路径长度等于m。链路效率是一种链路在缩短路径长度下的效率的测量。E值越高，对应的网络就越有效率。
3.3 随机网络ER模型
随机网络是最早的被研究的网络之一，并且在很长一段时间被用来作为研究真实网络系统最有力的武器。然而，自然界事实上并不是随机分布的，而是包含结构的。随机网络的标志性属性是“随机拓扑”导致高熵。稀疏随机网络也显示小世界效应——它们的直径随着少量随机链路的添加而快速收缩。
随机网络的生成过程主要有三种[9]。一个生成过程（Gilbert）是从一个完全网络开始，不断删除随机选择的链路，直到获得需要的链路密度为止；另一个生成过程（Erdos-Renyi（ER））是通过对随机选择的节点对之间插入边距直到达到指定规模的链路为止。Gilbert和ER过程，都以非零概率产生不连通的网络，而第三种生成过程（锚定的ER）提供一个以牺牲基本些随机性为代价来保证的连通图。锚定随机网络相对完全的随机网络，减少了孤立节点的出现。
总的来说，所有生成过程的目标都是为了随机化网络中度序列的分布。“完全随机”网络就是服从二项式度序列分布的网络。 3.3.1 Erdos-Renyi(ER)随机网络
ER生成过程是1959年由Paul Erdos和Alfred Renyi提出来的，是目前产生随机网络的标准方法。与Gilbert过程的不同点是，ER过程固定链路数m和节点n，并不需要概率变量p.
给定m和n，构建一个ER随机网络的算法如下： （1） 初始化：生成n个节点并从0到 进行编号； （2） 设置m：给定m值，且#links(链路数) = 0； （3） 重复以下工作，直到m=已插入的链路数为止：
a. 选择随机的节点：tail??Math.radom()?n； b. a.选择随机的节点：head??Math.radom()?n；
18
c. 循环出口：while(tail??head)head??Math.radom()?n
d. 去重：if(没有重复)就在tail和head宰插入一条新链路，并使#links加1.否则什么都不做。
需要注意的是，m必须小于n??n?1?/2?，否则会进入死循环。ER网络具有特定数目的链路，因此对于给定节点和链路数，其密度为2m/?n?n?1??，这就允许更精确地控制随机网络的密度。 3.3.2 随机网络ER模型
上世纪50年代，Erdos和Renyi建立了随机网络的ER模型[19]，他们采用前面叙述的ER随机网络生成方法构造随机网络。而具体对构造的随机网络G，假设有N个
2网络节点，每节点之间连接的概率为pER，则该随机图边数期望为pERCN条。当
pER=0时，表示任意两个节点之间都没有联系，网络总边数为零；当pER=1时，任
2意两个节点之间都有边相连，该图构成了一个完全的规则网络，网络总边数=CN；
当pER介于0到1之间时，网络节点度序列分布服从二项分布（Binomial Distribution）：
2kP?k??CNpER?1?pER?N?k
随机网络节点的度的平均值k?pERN，聚集系数C?k，网络的平均距离为N??lnN。N可以表示网络规模，当N较大时，随机网络表现出较小的聚集系统，lnk以及较小的网络平均距离。
由中心极限定理，当pER较小，而网络节点数N充分大时，该随机网络节点度序列分布近似服从一个泊松分布（Poisson Distribution）:
P?k??e???k/k!
其中，
kk??CN?1pER?1?pER?N?1?k
从而有??pER?N?1?。为了便于对照，这里给出在N=10000个节点的随机网
19
络中，不同pER值下，p?k?分布情况，如图3-3所示：
图3-3 随机网络ER模型度序列泊松分布
3.4 小世界网络WS模型
3.4.1 小世界概念
“小世界”的概念最初源于“六度分隔”的说法。而“六度分隔”的雏形，最先由一个叫凯伦斯（Karinthy）的作家1929年在其著作《链条》中提出来的[8]。凯伦斯在《链条》中写道：“为了证明当今世界上人之间关系紧密，一伙人中的一个成员建议做试验。他下赌注，说世界上几十亿人当中随便说出一个人，这个人只需最多说出5个相互认识人的名字，就能和指定的人拉上关系”。凯伦斯关于人和人之间最多需要5层关系联系起来的说法，成为了“六度分隔”概念最早的表达。“六度分隔”概念，是哈佛大学教授斯坦利?米尔格莱姆（Stanley Milgram）在1967年提出来的。
在人际关系网中，大部分人际关系可能都是“近程”的，例如家属关系、同学（同事）关系等，类似于规则网模型中的邻边；然而许多人都有远方的人际关系，例如移居海外的亲属、创业于边疆的同学等，类似于远程跳跃边，生活中有些人交友广泛、活跃，有些人则不然。如果你要找一个远程的亲戚或朋友帮你一些忙。你常常不得不“亲戚套亲戚、朋友托朋友”来找到这种关系。但是你发现原来想象的不知道要绕多大圈子才能找到的关系原来并不远，目的地其实就是长
20
时间不联系的近亲或者十分知己朋友的好朋友，他们可能给你帮很大忙。这就是“小世界”的体现，而在“小世界”中，“弱关系”起到了很大的作用。
马克?格兰诺维特（Mark Granovetter）在1973年发表的《The Strength of Weak Ties》一文中，提出了一个乍看起来非常荒谬的观点：“若论起找工作、获取消息、开饭馆，或者是传播最时兴的潮流，我们的较弱的社会关系比起自己所珍视的坚实的能起到更重要的作用??”。事实上，我们在生活中会有这样的感触：找工作时，最亲密的朋友往往帮不上忙。原因是他们跟自己处在同样的圈子里，接触的信息大部分跟自己一样。要获取新信息，必须依靠弱关系。事实证明[8]，从事管理工作的工人更可能通过弱关系（27.8%）而不是强关系（16.7%）获得工作机会信息。与最亲密的朋友相比，弱关系（或者熟人）是我们联系外部世界的纽带，由于活动范围不同，获取信息的来源也就不同。 3.4.2 小世界网络模型（WS模型）
为了回答为何群集现象普遍存在于真实网络系统中，瓦兹（Watts） 和斯绰伽兹（Strogatz）在1998年发表于Nature的文章[1]中，提出随机网络图与群集现象相结合的网络模型，那就是小世界网络模型（WS模型）。如图3-4：
图3-4 小世界网络模型[1]
图中可以看到，它从上节所述的规则网模型开始，以概率p随机地“重连”每条边（任选此边的一个端点不变，脱开另一端点，随机选择网络中另一节点为端点），同时保证两个节点之间最多一条边，且每个节点与自己不相连（即保持为一个简单图，没有自连接和重复边）。这样，当p＝0时，每个节点都有k个邻点，完全没有“随机跳跃边”，显示一个规则网络模型；而在0< p <1时，随机重连边的期望值是pNk（N??），显示一个位于规则与随机之间的模型；当p＝1时，所有边都随机重连，模型转化为一个ER随机网络模型。
21
下图3-5对ER模型与WS模型网络节点演化过程进行对比：
图3-5 ER模型和WS模型演化
图3-5(a)表示ER模型。随机网络中N个节点，互相之间连接的概率为pER，则系统中边总数n?pERN?N?1?/2.例中表示了具有N=10个节点，连接概率当pER?0时，网络中无边；而当选择一对节点以pER?0.2的pER?0.2的随机网络。
概率进行连接时，如图所示为演化过程，图中有n?9条边；对于pER?1的情况，网络演化成一个完全规则图。
图3-5(b)表示WS模型。小世界网络以一个带有相邻以及次邻边的三维晶体结构起始，初始平均连接数k?4，对于每一个节点，它可能重新连接的概率为pWS，节
点数N=10，则重连边数为n?2pWSN。对于pWS?0的情况，网络是一个带2N=20
条边的规则晶体结构；对于pWS?0.3，2pWSN?6条边需要重连；当pWS?1时，该网络是一个随机网络，对应的ER模型中，pER?k/N?0.4。
在ER模型中，总顶点数保持不变，总边数进行随pER变化；而在WS模型中，总数不变，总边数也不变，但重连的边数随pWS变化。而Watts和Strogatz已证明当0?pWS?0.01时，网络具有大的聚集系数，表现出小世界属性[14]。 3.4.3 小世界网络度序列分布
从上述可以看出，小世界是部分k-规则和部分随机网络的混合，因此小世界网络的拓扑介于k-规则网络和随机网络之间。Barrat和Weight通过以下观察，导出了一种小世界度序列分布的紧凑形式的表达式：
22