时间不联系的近亲或者十分知己朋友的好朋友，他们可能给你帮很大忙。这就是“小世界”的体现，而在“小世界”中，“弱关系”起到了很大的作用。
马克?格兰诺维特（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
(1) 如果典型节点u的链路没有重联，它的度不变；若其它节点链路重定向到
u时，度会增加。
(2) 不重联链路的概率服从二项式分布B?k,i,?1?p??，这里k?m/n,i?不重联
的链路数，p为重联概率。
(3) 其它节点链路重联到节点u的概率服从泊松分布P??1,d?k?i??d?k?，其
中，?1?pk是重定向链路的期望值，d=度数，i=重联到u的链路数。 (4) 节点u度数增加的概率等于联合概率B?k,i,?1?p??P??1,d?k?i?。 (5) 度分布h?d?等于在i?1,2,3,...,min?d?k,k?条链路上的联合概的总和。 因此，重联后具有d条链路的节点度分布：
min?d?k,k?h?d??其中，
?i?1B?k,i,?1?p??P??1,d?k?i?;d?k
?1?pk
B?k,i,?1?p????ik??1?p?pk?i
iP??1,d?k?i???pk?d?k?ie?pk?d?k?i?!
下图3-6给出当n=50,m=400和重联概率p=50%时的随机网络和小世界网络度序列分布：
图3-6 小世界网络度序列分布
23
3.4.4 小世界网络属性
小世界具有相对小的平均路径长度、高的聚集系数和可以调整的熵（根据重联概率p变化）。当p＝0时，平均聚集系数：C?3?K?2?4?K?1?，这里我们用大写的K
表示小世界模型对应的规则网中每个节点的常数度值。在0?p?1时，对于任一个节点，它的两个邻点仍旧是它的邻点的概率分别都是(1-p)，它们之间也邻接的概率也是(1-p)，因此小世界模型的平均聚集系数的期望值为：
C?3?K?2?4?K?1??1?p?3，
与N无关。当然，这只是一个近似估计。
小世界模型的平均距离解析计算曾经是一个比较困难，因而引起热烈讨论的问题，目前大家普遍接受的是纽曼(Newman)、穆尔(Moore)和瓦兹(Watts)用平均场方法得到的解析表示式[1]：
N1/dl?N,p??f?pKN?，
K??常数若u?1??4u??tanh?1若u?1? 其中：f?u???2u2?4u?u?4u若u?1??ln?u?/u???由此公式不容易看出平均距离对N的依赖关系。Watts和Strogatz定量地显示了平均聚集系数和平均距离对N的依赖关系，如图3-7所示：
24
