小世界网络模型的重正规划群分析外文翻译资料-毕设翻译网

小世界网络模型的重正规划群分析

M.E.J. 纽曼，D.J.瓦特

圣菲研究所1399海德公园路，圣达菲，NM87501，USA

1999年8月16日收; 1999年9月30日收到订正格式; 1999年10月21日由A.R.主教接收传达

摘要

我们研究小世界网络模型来模拟规则点阵和随机点阵之间的过渡行为。我们认为，随着随机度逐渐趋向于零，模型会出现具有发散特征长度的临界点。我们为模型提出了一个实空间重归一化组转换，并证明该转换在大系统大小的限制下是准确的。我们使用该结果来计算系统的单个关键指数的精确值，并且作为三个独立变量的函数来导出网络上两个节点之间的“分离度”的平均数的缩放式。我们通过广泛的数字模拟确认我们的结果。

关键词：小世界模型; 重正化组; 缩放; 相变

与物理学通常所处理的网格不同，许多真实世界的网络交互同时具有随机图和规则网格的属性。瓦特和斯托加茨最近提出了一个网络模型，通过采取规则的格子和随机“重新布线”一些边缘在这两个极端之间进行插值。结果发现图的特征在于高度的局部聚类（像规则的格子），但是也具有顶点间距短的特性，类似于在随机图中发现的距离，即使是对于相当小的密度重新布线的边缘。这些以小世界社会学现象命名的“小世界”网络为各种各样的系统的拓扑结构提供了一个模型，例如互联网，电网，神经元连接模式，甚至电影演员的网络。同时也发现小世界网络的结构特性对动力系统有着巨大的影响，并且可能对许多现实世界的应用程序有重大的影响，包括耦合振荡器，神经网络，生物进化，扩散过程和信息传播。

虽然这些听起来很吸引人，但瓦特和斯托加茨的结果主要基于计算机模拟，对于更严格的小世界模型分析理解我们将更受益。统计物理学的技术特别适合于这项任务，特别是从关键现象的研究中得出的技术。在本文中，我们认为小世界模型在极限中的关键点处，其中捷径数的密度趋于零，并且我们使用重正化组（RG）方法，计算该缩放的近似点处的模型的行为形式和描述关键区域的单个关键指数。以前的研究集中在一维版本的小世界模型，我们将从这个版本开始，将结果推广到更高的维度。在一个维度上，模型被定义在具有L个站点和周期边界条件的晶格上。最初，每个站点连接到所有其邻点，直到在某个固定范围k内，形成具有协调数Z=2k的网络。然后通过以概率p独立地重新布线kL连接中的每一个来引入随机性。“重组”在本文中意味着移动的一端连接到一个新的随机选择的节点。因此，网络的行为取决于三个独立的参数：L，k和p。在本文中，我们将研究在随机选择的站点对其间添加捷径的模型的轻微变化，但没有连接从规则网格中删除的模型。对于大L，这对于直到次序为的网络的顶点之间的平均间隔没有差别。在顺序和更高，它确实起着作用，因为原来的小世界模型在这种情况下不好定义---有一部分晶格与其余部分断开连接的概率有限，因此对顶点之间的平均距离做出重要贡献，这使得在所有网络上的平均距离也是无限的。我们的变体不会遇到这个问题，这使得分析显得更简单。在图1中我们展示了一些小世界网络的例子。

emsp;

图1中描述的计算中使用的RG变换：（a）用于k=1系统的变换; （b）用于kgt;1的变换，在k=3情况下。站点的阴影表示它们如何在变换下分组。

我们测量的基本观察数量是网络上一对顶点之间的最短距离，在网络上所有的对上和在所有可能的随机性实现中取平均。这个我们记为的数量有两种行为方式。对于足够小的系统有比平均一个格子上少得多的捷径数，iota;受规则晶格的连接支配并且可以被设置随系统的尺寸L线性增加。当p固定时，晶格变大，平均捷径的数量将最终变得大于一并且iota;会开始变大为log L。这两个方法之间的过渡发生在一些中间系统大小为L=xi;里，从上面的论点，我们可以设定xi;为一个值使数字捷径数pkxi;=1。换句话说，我们设定xi;在小p的极限上发散为xi;~，数值xi;在常规统计物理学的一个相互作用系统中起着类似于相关长度的作用，它的分散没有留给小世界模型特征长度刻度而是基本晶格间距。因此模型在p=0时具有相变，正如我们看到的，这导致了接近转变的区域中有限大小特定的缩放行为。注意，在p=0处的相变是单侧的，因为p可以取小于零的值。在这里过渡类似于过渡其他一维系统，例如一维键，站点渗滤或一维Ising模型。

巴特勒米和阿马拉尔上面提出的论据，虽然大抵是正确的，但一些细节方面会有纰漏。他们认为长度xi;发散为xi;~p-tau; （1），但在tau;由缩放参数给出的值1意见不一。在上，他们推测tau;=。另一方面，巴拉特给出了一个简单的物理论证，表明tau;应该大于或等于1，与此矛盾。除此之外我们在本文中证明，事实上tau;对于的所有值恰好为1。

让我们先来考虑最简情况下的小世界模型，即k=1时。如上所述，平均距离iota;的长度近似等于L（Lxi;）同时L的对数远大于xi;的对数。如果xi;远大于1，这意味着iota;应该遵从有限尺寸标度律，从而得出iota;=Lf（L/xi;）（2），f（x）是一个通用的缩放函数，其限制条件为

（3）

事实上，很容易看出f（x）在x趋近于0时的值为四分之一。巴特勒米和阿玛拉尔先前已经提出了一种与此类似但不完全相同的缩放定律，用于小世界模型，虽然他们提出的这种缩放类型证明在模型中不存在相变，但我们认为在一个适当情况下存在iota;为一。

我们现在假设,在临界区，xi;取1，我们不知道tau;的指数的值。因此我们可以把公式改写成iota;=Lf（）（4）。我们已经知道了函数f（x）中的乘法常数。但除此之外它与之前的尺度函数是一样的，并且有同样的限制条件。
现在考虑到真实空间将RG变换成k=1小世界模型中, 我们在相邻对站点创建一个相同网格数的半一维晶格（我们假设晶格的尺寸L是偶数，如果我们在任何规模的组织块平分L，转换工作将会是正常的, 如果我们阻止任何大小的组分割L）如果一个中的任一原始顶点连接到另一个中的任一原始顶点，则在重新归一化的点阵上连接两个顶点。这包括快捷键连接。该变换在图1a中示出。晶格尺寸L=24。

在变换下晶格上的快捷方式的数量是保守的，因此基本参数L和p根据（5）重新归一化。

以正确的概率变换生成重新归一化的网格上的快捷方式所有可能的配置，我们可以轻易看出在任何两个站点i和j之间找到捷径的概率是均匀的，与重新归一化之前和之后的i和j无关。

几乎在所有情况下，通过我们的变换，任何两个顶点之间的最短路径的几何形状都不变，且直接显示几何结构改变的顶点对数对于大L和小p是可忽略的。沿着围绕周边延伸那些部分的环的特定路径的长度平均减半，并沿着捷径保持相同。对于大L和小p，沿着捷径的长度部分趋于零，因此可以忽略。因此：

（6）

等式5和6构成的RG方程，L1，p1。代入式4后我们得出：

（7）

现在我们转向kgt;1的情况。为了处理这种情况，我们定义了稍微不同的RG变换：我们将k个组中的相邻站点分组，使用与之前相同的规则分配连接。该变换在图1b中示出。对于尺寸L = 24的晶格，其中k=3。在重复变换下保留网络中捷径的数量，给出以下用于参数的重新归一化方程：

（8）

注意，在大L和小p的限制下，平均距离iota;完全不受影响; 沿着连接两个远处站点的路径的顶点数量减少k，但是可以在一个步骤中被遍历的顶点数减少相同的因子，并且两个顶点相抵消。出于同样的原因，如前所述，这种变换在大L和小p的限制下是精确的。

我们可以使用这个第二个变换将kgt;1的任何网络转换成k=1的对应网络，然后我们可以使用之前给出的参数

因此，我们得出结论，对于k的所有值，指数tau;= 1，并且从等式8代入等式4，一般小世界网络必须遵守缩放式：

（9）

对于L的导数远大于一和p的导数远小于一，此式应正确，这意味L/Kgt;gt; 1和p lt;lt; 1。这些条件中的第一个是不太重要的---它仅仅确保我们可以忽略对iota;估计中出现k的不准确度，因为格点上的位置通过RG变换被四舍五入为k的最接近的倍数。第二个条件很有意思，但是有必要确定平均行驶距离。与在环的周围行进的距离相比，网络中的捷径很小。这个条件告诉我们，当我们移出贴近转换由(9)控制的缩放制度,进入真实的随机网络, 其中违反(9)并且已知iota;得出log L / log k[12]。这意味着我们需要使用p的值减去,随着k的增大，如果我们希望看到净缩放行为，或者相反，真正的随机网络行为应该在网络中可见p或更大的值。

我们通过广泛的小世界模型的数值模拟验证了我们的预测。我们已经计算了各种网络上的所有点对之间的最小距离，并且对结果取平均以求出iota;。对于大小为L（协调数z = 2）的系统，对于k = 1，等于从128到8192的二次幂，以及p=1x到3x，和对于k=5（z=10），L=512到32768和p=1x到3times;。每个计算在随机性的1000个实现中取平均。在图2中，我们显示我们的结果作为iota;k/L对pkL的值进行绘制。等式9预测当以这种方式绘制时，结果应该折叠到单个曲线上，并且如图所示，它们的确做到了，这是一个合理的近似。

如上所述，巴特勒米和阿马拉尔还进行了小世界模型的数值模拟，并提取关键指数的tau;=。在图2的插图中，我们得到了k=1时根据公式绘制的模拟结果

（4）中使用该值为tau;.如图所示，在这种情况下，数据崩溃明显比tau;=1更差。有趣的是当问到巴特勒米和阿马拉尔他们是如何得到的结果.似乎很可能是由于查看的系统太小所以不能显示真正缩放行为而产生的问题。在我们的计算中，我们发现良好的缩放L/kgt;60. 巴特勒米和阿马拉尔检查k=5,10和15(Z=10,20,30)的网络，所以我们应该期待找到良好的缩放行为,大约600的L值。但是，巴特勒米和阿马拉尔研究的系统的大小从大约L=50到在大多数情况下约为500，在任何情况下都不超过L=1000。因此，它们的计算与缩放方案没有重叠，或者只有一个小重叠，因此我们不希望在其结果中发现tau;的真实值的典型行为(见脚注3和[11])

可以将这里给出的计算推广到建立在尺寸d大于1的网格上的小世界网络。为了简单起见,我们首先考虑情况k=1。如果我们在具有线性尺寸L的维度d，最近邻顶点之间的连接以及添加有重新布线概率rho;的快捷方式中构造正方形或立方体晶格，则如前所述平均顶点 - 顶点距离对于小L线性地与L成比例，对值大的L，并且跃迁的长度尺度xi;根据等式 1为小P。因此，缩放形式（4）也适用于一般的d。我们的RG变换的适当推广涉及将方块或立方块组合在一起，并且L，p和iota;的值满足：

作为示例，我们在图3中示出对于d=2情况的3个数值结果，对于L等于从64直到1024的二次幂和对于从p=3times;到1x的每个系统尺寸的6个不同的值。结果根据等式4，tau;=，如图所示，它们再次完全折叠到单个曲线上。

对于kgt; 1，可以进行许多归纳。最简单的应该是在其间隔为k或更小的所有顶点之间沿着晶格的主轴添加连接。这产生具有平均配位数z=2dk的图。通过阻塞边缘k的正方形或立方体块中的顶点，我们可以将该系统变换为k=1的系统。即RG等式的适当推广

图3. 如文中所述，基于网络中二维正方形晶格的数值数据折叠，在所有情况下，误差棒小于数据点。

（8）

或者，我们可以重新定义我们的缩放函数f（x），使得iota;K/L作为的函数给出。以此形式进行写入可以清楚地看出，在从大到小的行为过渡中，网络中的顶点的数量在任何数量的维度上分歧为。

kgt; 1的另一个可能的推广是在边2k的正方形或立方体区域内的所有位点之间添加连接。这给出了在缩放形式中对k的不同依赖，但是tau;仍然等于1/d。

总而言之，我们使用渐近精确的实空间重整化组方法研究了瓦茨和斯托加茨的小世界网络模型。我们发现，在所有维度d中，模型在极限中具有临界点，其中捷径数p的密度趋于零，并且特征长度xi;根据连接范围k的所有值的tau;= 1/d的xi;~而发散。我们还推导出了一般的有限大小，其描述了作为p，k和系统尺寸L的函数的平均顶点 - 顶点间隔的变化。我们进行了广泛的数值计算，证实了我们的分析结果

致谢

这项工作部分由Santa Fe研究所和来自NSF（授权号PHY-9600400），DOE（授权号DEFG03-94ER61951）和DARPA（授权号ONR N00014-95-1-0975）的资助支持

由初始冲击触发的大级联在复杂网络中是常见的。耦合的地图晶格在过去几十年被广泛用作复杂系统的动力学模型。在这里我们调查耦合地图晶格与不同的拓扑的级联故障。我们发现级联故障在小世界和无规模耦合映像晶格中比在全局耦合映射晶格中更容易发生。

在许多真正复杂的网络中观察到级联故障。美国历史上最大的停电发生在2003年8月14日，这是一个典型的级联电网故障示例。由最初的冲击导致整个网络崩溃和不同网络中级联故障的特点是什么？虽然复杂网络中级联故障的趋势远未完全理解，但它必然受网络结构和网络组件动态行为的影响。特别是自从发现复杂网络的小世界和无规模的特征，一些研究人员已经研究了级联失效现象和复杂网络的拓扑之间的关系

耦合映像晶格（CML）已经在过去几十年被广泛研究，以模拟复杂系统的丰富的时空动力学行为。在大多数这些研究中，耦合映像晶格通常假定具有规则耦合（诸如全局耦合或最近邻耦合）拓扑。最近，一些研究人员已经开始研究动态行为，例如CML与小世界或尺度耦合拓扑的同步。

在这项工作中，我们提出了基于CML的级联故障模型。我们调查了在具有不同耦合拓扑的模型中的级联故障，包括全局耦合，小世界耦合和无标度耦合。我们发现单个节点的击穿足以触发整个网络崩溃，如果外部的振幅单个节点上的扰动大于阈值。此外，我们发现全局耦合映像

剩余内容已隐藏，支付完成后下载完整资料

英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料