英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
摘要--本文展示了一个小世界网络的代数连通性的相变现象。一个图的代数连通度是第二小的拉普拉斯矩阵的特征值和测量网络的一致性问题解决速度。我们表明显着地增加一个普通的复杂网络的代数连通性的1000倍或更多，而不增加新的链接或节点到网络是可能的。这意味着一个问题即如何可以很快地解决某些小世界网络的高速信息网络的网络设计算法。我们的研究依赖于一个程序为“随机重新布线”，这是由Watts和Strogatz（自然杂志，1998）提出的。大量的数值计算结果对我们的要求和猜测提供了支持。我们证明了拉普拉斯散谱的意思一个复杂的网络保持不变的随机重新布线。同一概念渐近适用于无标度网络。增加复杂的代数连通性之间的关系网络和鲁棒性的链路和节点故障也显示了这一点。使用渗流理论分析网络的鲁棒性是一种替代法。在随机矩阵理论上我们还展示了一些连接图：即使我们的猜想和一些开放性问题。
关键词：小世界网络，网络系统，一致性算法，相变，拉普拉斯图，代数连通度，网络的鲁棒性、随机矩阵
I.简介
大型工程，生物，和社会系统中的复杂网络是丰富的。一些例子包括电力网络，代谢和基因网络[ 17 ]，共同作者网络的科学家[ 27 ]，振荡器的生物网络[ 19 ]、[ 18 ]、[ 24 ]、[ 39 ]、[ 44 ]，经济网络[ 15 ]，传感器网络[ 10 ]，[ 30 ]，[ 7 ]，[ 38 ]，网络无人自主车辆群[ 32 ]，[ 36 ]，[ 6 ]，[ 25 ]，及自组织生物群[ 41 ]，[ ]。关于复杂网络的最近的调查，读者可以参考[ 40 ]，[ 28 ]。
1998年，Watts amp; Strogatz [ 42 ]介绍了一种名为小世界的网络，它在正规网络和随机网络之间使用一个单一的参数。小世界网络就是相对特征长度小的网络。在一个小世界中，任何2个节点可以使用几个步骤，但是却很大尺寸的网络链接。例如，世界各地Web（WWW）有N = 8times;108节点但其特征长度只有18.5【3】。
Watts和Strogatz的小世界模型激发了研究人员从多个领域在研究复杂网络的拓扑性质的浓厚兴趣。其中在自然科学领域，网络研究的基本测度包括：度及其分布特征，度的相关性，集聚程度（见【42】及【48】）及其分布特征，最短距离及其分布特征，介数及其分布特征，连通集团的规模分布。对这些方面做出重大贡献的研究人员来自统计物理、计算机科学、经济学、数学生物学、通信网络、电力网络等领域。
在大多数工程和生物复杂系统，节点有一个动态的，他们不是标签或演员的名字。换句话说，“现实生活”工程网络是动力系统的互联。这同样适用于生物网络，包括基因网络和耦合神经振荡器一类的广泛的例子。从层次性的系统与控制理论来说，稳定性能动态代理网络的集体稳态是有利的。这激发了对复杂网络的频谱特性的探索。在过去，随机网络的关系很少有人关注研究。本文是对理解复杂网络的拉普拉斯谱和超快信息网络设计中的应用行为的第一步。
我们使用一致性问题[ 35 ]，[ 33 ]作为一个框架来表达我们的想法，以此解决关于复杂网络的连接和非超快光谱特性之间的分布式决策方案用于相互作用基团的问题。求解一致性问题的分布式计算直接影响传感器网络和数据融合[ 38 ]，负载平衡[ 21 ]。此外，耦合振子的同步[ 44 ]、[ 19 ]、[ 18 ]、[ 24 ]，在过去的35年收到了巨大的关注，这是网络系统中对于所有节点计算的频率结果的一个非线性的一致性问题的特殊情况。所以，代数连通性是（局部）同步速度的测量。
复杂网络的第一步是在五十年前由 Erdouml;s amp; Reacute;nyi (ER)提出的随机图。通过以概率p连接任意对顶点的随机图可能是研究最完善的随机网络。如果ER随机图中这种特征概率p超过了某个临界值pc即p gt; pc asymp; 1/n，这就意味着在这个网络系统中有一个巨大的组件间链接[9], [40]。这种现象是第一个已知的组合相变的例子。组合和算法的其他相变现象后来在离散数学的发现和计算机科学领域被发现。
随机的下一代网络包括三个模型：1）Watts和Strogatz（WS）发现的小世界网络[ 42 ]，2）Newman, Moore, amp; Watts (NMW)发现的半正则小世界网络[ 29 ]，3）Barabaacute;si amp; Albert (BA)发现的无标度网络（(如 www)）[ 1 ]。我们将细致的描述WS和NMW网络模型，将BA模型留到未来讨论研究。通过研究我们发现ER模型是不够的，因为它是不能保证连接的正确性，除非图是相对密集的。这就是为什么我们专注于WS小世界模型和NMW小世界模型。
这是本文的一个概要：从系统和控制的角度来看一些背景共识的问题在第二节。小世界网络以及它的半正则版本在第三节。一般网络的随机重连过程主要在第四节。我们在小世界网络和网络弹性的拉普拉斯谱特性的主要结果和猜想列于第五章。对于小世界网络的拉普拉斯光谱特性与网络弹性之间联系得到的理论结果在第六节讨论，最后，结束语在第七章。
2.网络一致性问题
考虑一个网络的集成节点 x˙ i = ui和拓扑G = (V, E)，其中每个代理只与周边在G = (V, E)上的节点 Ni = {j isin; V :{i, j}isin; E} 交流。这里V = {1, 2,..., n}和E sub; [V ]2
分别设置为网络的节点和边/链接，在[35], [33]中,Olfati-Saber amp; Murray表明如下的线性动能系统解决了一致性问题。
x˙ i(t)= 「 (xj (t) minus; xi(t)) (1)jisin;Ni
更确切地说，让a1,..., an isin; R均为常数n，然后令初值设定xi(0) = ai, ，所有节点的状态都会逐渐趋于平均值value amacr;= 1/n， ai 印证了网络是互相连接的。节点的集体动力在（1）中可以表示为
x˙ (t)= minus;Lx(t) (2)
其中L = L（G）是图G的拉普拉斯矩阵。拉普拉斯定义为 L = D minus; A，D是G的一个i元对角矩阵。让我们用拉普拉斯变换表示L的特征值，lambda;1 le; lambda;2 le; · · · lambda;n.
请注意，拉普拉斯矩阵总有一个特征值为0的lambda;1 = 0对应x = (1, ...,1)T的特征向量。此外，如果G是连通的，那么lambda;2 gt; 0 [ 13 ]。显然，网络中的一致性问题的分析，降低了对网络拓扑的拉普拉斯谱分析。特别是lambda;2是收敛速度的测量（或性能）的一致性算法（1）[ 33 ]。lambda;2由Fiedler [ 12 ]命名的代数连通度图，图来源于下列不等式：
lambda;2(G) le; nu;(G) le; eta;(G) (3)
nu;（G）和eta;（G）分别是节点的连通度和图的边连通度（见[ 4 ]的定义）。根据这一不等式，具有相对高的连通度的网络对节点失效和边失效有强大的稳定能力。这种程度的鲁棒性下界是［lambda;2]。
一个时滞网络控制系统的一致性算法有如下形式[ 35 ]，[ 33 ]：
x˙ i(t)= jisin;Ni{xj (t minus; tau; ) minus; xi(t minus; tau; )} (4)
x˙ = minus;Lx(t minus; tau; ). (5)
我们假设，在所有环节的延时等于tau;（在一般情况下见[ 35 ]）。在[ 33 ]中（5）给出了对于系统的稳定的充分必要条件为
tau; lt; tau;max =2lambda;n （6）
因此，lambda;N是延迟达到一致性鲁棒性延迟的措施。
本文的主要结果是，lambda;2对于普通的网络可以增加多个数量级，通过改变代理间的信息流克不增加的总数网络的链接。此外，这一变化对lambda;N的影响可以忽略不计（系统保持鲁棒性的延迟）。图上的共识问题的一些变化包括以下几个方面：网络拓扑切换[ 16 ]、[ 33 ]、[ 26 ]、[ 34 ]、[ 33 ]上有网络一致性，[ 26 ]，并异步一致[ 14 ]。
3小世界网络
. 小世界现象是某些复杂的特征网络，其中任意两个节点可以使用一些链接[ 23 ]连接。这意味着两个节点之间的平均距离（即特征长度）是比较小的小世界。
1998年Watts 和Strogatz（WS）[ 42 ]介绍了一种介于随机网络和均匀网络间的网络模型（见图1）。他们证明了广阔的前进行社会、生物和物理的复杂网络，属于小世界网络的范畴，在美国西部的电力网络，一个名为 C. Elegans的线虫的神经网络，网络的科学家，和演员发挥在同一网络电影里[ 42 ]，[ 40 ]。
为了构建一个小世界网络，开始的环上的三维晶格具有n个节点，每个节点连接到其范围距离K最近的邻居。我们表示这格为G0 = C（n，k）。然后，重建的每一个环节都以概率p改变一个均匀随机的连接端点。不允许自我循环或重复的链接。（注：一个精确的数学布线算法后可以代表任意一个网络）图1表示不同的参数p所对照不同的随机布线方式。
为了使人们更好地了解小世界网络模型,Watts定义了小世界网络的三个特性。第一个特性是连接各个节点之间最短的路径长度,这是整个网络中所有节点对路径长度的平均值。第二个特点是集聚程度,它代表了两个节点之间通过各自的相邻节点连接在一起的可能性,当然它们之间可能直接连接,即网络的集聚度。Watts在文中表明由于以上的两个参数,高度结构化的网络有长路径和大的聚合度,而随机网络则有段路径长度和很小的集聚度。一个小世界网络展示了与随机网络相近的路径长度,但却拥有高聚合度。第三个特性就是对数路径,所以对任何规模的网络都会随着网络图形变得越来越巨大而网络却保持相对短的路径长度。
Newman, Moore， Watts（NMW）[ 29 ]介绍了一种另外的小世界网络模型的形式：有规则的格子加上随机图。重组是不必要的。随机在两个节点中每个加phi;个边。NMW模型平均有NK NKphi;链接。 用平均场统计理论我们指出NMW模型为半正规化的小世界网络。半正则小世界模型可以有效地作为WS模型的一种近似模型。两模型度分布是已知的，可以找到[ 28 ]。
我们的主要贡献是表明，代数和一个小世界网络的连通度可超过1000倍，比普通的网络。这意味着，小世界网络去苏通过光谱的相变现象，是前所未知的。这个光谱相变允许在小世界网络的超快达成共识。
备注1。通过一个图的谱性质，意味着我们的拉普拉斯矩阵的基本相符，不同于一个图的邻接矩阵的谱性质考虑光谱特性发生在[ 11 ]。邻接矩阵的谱对系统稳定性没有关联（2）。
4随机重连算法：网络演化
随机重连过程[ 42 ]可以一般化到网络中任意拓扑的方式简单的病房。对于未来的应用，我们正式描述这种算法的细节。这种方法的副产品是，小世界网络可以得到三要素的动态图[ 22 ]有限时间演化的限制：非确定性图图解动态随机重连算法指定的初始状态是一个普通的格子，和终端的状态，是一个小世界网络。
小世界网络中的谱相转变 （主要结果）
在这一部分，我们的行为特征的代数连通度和lambda;n是基于复杂网络上的小世界网络一套系统的数值实验。这让我们有了一个正式的猜想，对小世界网络中lambda;2和lambda;4，以后可以用不同的理论解决。下面是指导我们的研究的一些激励问题：
1.什么时候lambda;2（P）作为P的结果增加？
2.lambda;2（P）是P的单调函数吗？
3.随机重连增加lambda;2（GT（P））（平均年龄为固定P）是随时间的函数的步骤吗？
4.lambda;2（P）100，1000或10000增加，p的区间是否有变化？
5.在重新布线后lambda;N（P）有何变化？
到目前为止，对小世界网络的研究并没有解决上述问题，没有得出分析或实验研究的光谱特性。解决这些问题的关键，是进一步认识相互关联的动态系统工程和生物系统中出现的复杂网络特性。这方面的知识特别有益于超快信息的设计信息网络。
在表格1中我们得到了大量的小世界网络中G(p)对每个p的指定初始状态。参数选择的对数比例为0.01至1（25个数据点）。事实上，对于0＜P＜0.01，可以观察到lambda;2（P）无显著变化。表格的最后一项（或G4）对应于一些图形参数，这些图形参数在[42]中图二被用来创建数据库了。表中的所有条目都满足k asymp; log(n)/2 meaning that m = |E| = O(n log(n))。
定义1。（代数连通度增益和鲁棒性的延迟）让lambda;（P）=lambda;（G（P）），注意，G（0）= G0。我们指的gamma;2（P = 2）lambda;（P）/lambda;2（0）的代数连通度增益G（P）。此外，gamma;N（P）=lambda;N（P）/lambda;N（0）称为鲁棒性的措施来延缓网络G（P）（如gamma;N（P）的增加，网络可以容忍较小的延迟）。
小世界网络中的代数连通度增益G（P）是从规则网络G2，G3，G4进化演变二来的（定义在表I）如图2所示。gamma;2(p) = lambda;2(p)/lambda;2(0) 有一个S形曲线，它基本上是相同的各种网络参数。图中的每个数据点是通过平均超过10节点随机重新布线网络而得到的。从模拟实际数据运行的得到的数据是为图3里的G4铺垫的。以下是一些观察和评论：
可以观察到开始的临界值代数连通性增益中的2个相变。在[ 42 ]中的小世界现象的出现的G0 = C(1000, 5)这个临界值大于参数值103倍。显然，对于N = 1000个节点的网络，lambda;2可提高1500倍以上的点间隔。随机重连高P不一定增加lambda;2复杂的规则网络。事实上，根据图2（b），P = 1重可能导致的增益小于网络gamma;lowast;。随机重新布线的规则网络，是不是足够复杂，并不一定会增加lambda;2（详情见[ 31 ]）。lambda;
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[147826]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
