英语原文共 3 页，剩余内容已隐藏，支付完成后下载完整资料
“小世界”网络的集体动力学
Duncan J. Watts ， Steven H. Strogatz
美国纽约（14853）伊萨卡,康奈尔大学,Kimball 学院理论与应用力学系
....... ........... ............ ............ ............ ........... .........
连结动力系统的网络已被用于为生物振荡器1-4、约瑟夫森结阵列5-6、应激介质7、神经网络8-10、时空博弈11、基因控制网络12以及许多其它自组织系统建立模型。通常，这些模型的拓扑结构被假定为完全规则网，或完全随机网。但许多生物网络、技术网络和社会网络却介于这两种极端的网络之间。在这里我们探究能够直达两种极端网络中间地带的简单网络模型：即通过重新连接规则网络中结点之间的连线来增加该网络的无规则性。我们发现这 些网络能够像规则网那样具有高度的集群性，又像随机网那样具有短的特征路径长度。由于具有类似小世界现象（即众所周知的六度分离15），我们把它们称为“小世界”网络13-14。蠕线虫的神经网络、美国西部的电力网络以及电影演员的协作网络已被证明是小世界网络。具有小世界连接的动力系统模型显示出能增强信号的传播速度、计算能力和同步能力。尤其是，传染性疾病在小世界网络中传播比在规则网络中要容易得多。
为在规则网络和随机网络之间生成新的网络，我们考虑以下随机重新连线过程（图 1）。从一个有n个顶点以及每个顶点有k条边的环形网络开始，以概率p随机给每条边重新连线。这一连线过程允许我们在规则网(p=0)和随机网(p=1) 之间生成各种网络，因此就能探查我们还知之甚少的中间区域（0lt;Plt;1）网络的特性。我们用特征路径长度L(p)和集群系数C(p) 来量化这些网络的结构特性，如图 2 所示。这里L(p)度量图中两顶点之间的特征距离（一种整体特性），而C(p)度量邻域之间的特征集群性（一种局部特性）。我们所关心的是这一网络具有许多稀疏连接的顶点，但却没有稀疏到使网络图面临失去连通的危险。具体来说，我们需要ngt;gt;kgt;gt;ln(n)gt;gt;1,其中 kgt;gt;ln(n) 保证随机网络图是连通的16。在这种状态下，我们发现当p→0 时，L～n/2kgt;gt;1 以及C～3/4，而当p→1 时，Lasymp;Lrandom～ln(n)/ln(k)以及Casymp;Crandom ～
k/nlt;lt;1。这样，当p=0 时的规则网络是一种高度集群的大世界网络，此时 L随n 线性增长，
而当p=1 时的随机网络是一种低度集群的小世界网络，此时 L仅随n成对数增长。这些有限的例子可能导致人们推测大 C总是与大 L关联，小C总是与小L关联。
相反地，图 2 揭示出有一个p的广阔区间,在这个区间上L(p)几乎与Lrandom一样小，但
C(p)gt;gt;Crandom。这些小世界网络是通过引入几条长距离的边造成L(p)的直接下降所致。这样的“捷径”连线会以比Lrandom方式不同方式连接更远离得多的顶点。对于小p,每个捷径对L有 一个高度非线性作用，不但缩小了它连结的一对点之间的距离，而且也缩小了它们所处的邻域之间的距离，以及邻域的邻域之间的距离等。相比之下，从一个集群邻域中移去一条边以建立一个捷径最多对C有线性作用；因此，即使L(p)急速下降，对于小P来说，C(p)仍然几乎不变。这里的重要意义是在局部层次(由C(p)反映)上向小世界网络的转变几乎是无法觉察的。为检验这些结果的稳定性，我们已经试验了许多不同种类的原始规则网络图，还有随机重新连接的不同算法，所有都给出了质量相似的结果。唯一的要求是改写连线边的方式必须会比Lrandom方式连接更远离得多的顶点。
以上理想化的结构揭示了捷径的关键作用。它暗示小世界现象可能在有许多点的稀疏网络中普遍存在，甚至捷径只占一个微小比例就足够了。为验证这一观点，我们计算了以下三个网络的L和C值，它们是特色电影（来自http://us.imdb.com网站的数据）中演员的合作图，
美国西部的电力网，以及蠕线虫17的神经网络。所有三个网络图都有科学价值。电影演员合作图是社会网络的替代品18，对它的说明相对比较容易。对于传统以P. Erdouml;s的观点(部分数据来自http://www.acs.oakland.edu/,～grossman/erdoshp.html)为中心的数学合作研究图也是类似的。电力网格图是与电力网络19的效率和稳定性相关的。而线虫是完全反映神经网络的唯一例子。
表 1 说明三个图都是小世界网络。这些例子不是精心挑选的；之所以选它们是因为它们内在的价值以及可以得到它们的完全连线图。这样，小世界现象就不仅仅是社会网络13，14的奇异特性，也不是理想模型的赝像——它或许对自然界许多大型稀疏网络是一种普遍现象。
表 1 小世界网络的实际案例
---------------------------------------------------------
Lactual Lrandom Cactual Crandom
⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯
|
电影演员合作网 |
3.65 |
2.99 |
0.79 |
0.00027 |
|
电力网 |
18.7 |
12.4 |
0.080 |
0.005 |
|
线虫 |
2.65 |
2.25 |
0.28 |
0.05 |
⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯
三个真实网络的特征路径长度L和集群程度C，与顶点(n)数量相同以及每个顶点拥有边的平均数量相同的随机网络图之比较。(演员: n=225,226, k=61.电力网: n=4,941, k=2.67.线虫: n=282, k=14.)网络图定义如下：如果两个演员在一部电影中共同表演，就把他们用一条边连接起来。我们把讨论限定在这个网络图的巨大连通分支上16，这个分支包括到 1997 年 4月为止存储在因特网电影数据库(来自http://us.imdb.com)里所有演员的90%。对于电力网络来说，顶点代表发电机、变压器和变电站，边代表它们之间的高压传输线。对于蠕线虫来说，如果两个神经细胞由突触或缝隙连接来连接的话，一条边就会把这两个细胞连起来。我们把所有的边看作是无向的和无权重的，把所有的顶点看作是相同的，并承认这些假设是粗糙的近似。所有三个网络显示了小世界现象：L Lrandom,但C gt;gt;Crandom。
我们现在研究动力系统的小世界连通性的功能意义。我们的试验案例是一个故意简化的传染性疾病的传播模型。人口结构由图1所描绘的图的家族建模。在时间t=0 时，一个单一的传染性个体被引入原来健康的人群。经过一段时期的疾病传染后，传染性个体就会被永久移去(由于免疫性或死亡)。在这一时期，每一个传染性个体会有概率为 r 的机会把疾病传染给它的每个健康邻居。在随后的各时间步中，疾病沿着网络图的边进行传播，直到它传染了整个人群，或在传染了部分人群后逐渐消失。
图1 在不改变网络图中顶点或边的数量的情况下，在规则环形网络和随机网络之间插入随机改写连线过程。我们从有 n 个顶点的环形开始，每个顶点由无向边连到它的 k 个最近的邻点。为清楚起见，在这里的示例中 n=20，k=4,而大得多的 n 和 k 用在本文的其它地方。我们选择一个顶点和一条边顺时针方向连到离
它最近的邻点。我们以概率 p 重新连接这条边到一个在整个环上随机选择的顶点，连接时不允许出现重复的边；如果有重复的边，就不连接这条边。我们重复这一改写连线过程，顺时针方向沿环移动，依次考虑每一个点直到一圈完成。然后，我们考虑连接该顶点到离它顺时针方向次近的邻点的那些边。像前面一样， 我们以概率 p 随机为这些边的每一条重新连线，继续这一过程，绕环旋转并且每一圈之后考虑向外面更远的邻点连接，直到原来网络的每条边都已经被改写完毕。(因为在整个图中有 nk/2 条边，所以 k/2 圈之后重新连线过程结束。)在不同 p 值条件下的三个连线结果如图所示。对于 p=0,原始环不变；随着 p 值的增加，网络图变得越来越紊乱直到 p=1,所有的边都是随机重新连线的。我们的一个主要结论是对于 p 值的中间值，曲线图是一个小世界网络：像规则网一样高度集群，却像随机网一样有较短的特征路径长度。(见图2)
图2 图1中所描绘的随机重新连线的网络图族的特征路径长度L(p)和集群程度C(p)。这里L被定义为两顶点之间最短路径边的数量，是所有两顶点之间最短路径边的平均值。集群程度C(p)定义如下。假定每一个点v有kv个邻点；于是在它们之间最多可以存在kv(kv-1)/2 条边 (这种情况发生在当v的每一邻点都连到每一个v的其它邻点时)。以Cv表示实际存在的边与允许存在的边的比值。定义C为所有v的Cv的平均值。对于朋友关系网络，这些统计结果有直观意义：L是在连结两个人的最短链中具有朋友关系的平均数量；Cv反映的是V的朋友在多大程度上相互之间也是朋友；这样C度量的就是一个典型朋友关系中的集群性。数字中显示的数据是图 1 所描绘的重新连线过程 20 个随机实现的平均值，并且已经被一个规则网络的L(0)和 C(0) 值规范化。所有的网络图有n=1,000 个点，并且每个顶点平均有k=10 条边。我们注意到一个对数水平的标度被用于解决L(p)值的快速下降，相当于开始表现出小世界现象。在这一下降过程中，对于规则网络来说C(p)几乎保持不变，这标志着在局部层次上向小世界网络的转变几乎是无法觉察的。
由此出现了两种结果。第一种，在疾病传染了一半人群时的临界传染性rhalf对于小p值来 说急速下降(图 3a)。第二种，不管其结构如何，对于一种有足够的传染性以传遍整个人群的疾病，整个传染需要的时间T(p)类似于L(p)曲线(图 3b)。这样，传染性疾病在小世界网络中预计传播得更容易
全文共5119字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[2557]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
