复杂网络作业.doc

无标度复杂网络中的瞬时同步现象
摘 要：网络在自然界和人类社会中无处不在，常见的网络有生态网、万维网、人际关系网和交通网络等等。对真实网络特性的解释使得复杂网络成为了近年来的研究热点之一。自从发现瞬时过渡转变现象以来，集体性的瞬变现象得到了极大的关注。过渡一词是用来表述网络或网格在连接度上的急剧变化。实验证明，不同的网络增长过程会带来网络的一阶突变，即不连续的变化。本文着重探索当在网络拓扑结构k和动态特性w之间存在关系时无标度网络的一些特性。本文首先介绍了复杂网络的发展过程，然后，根据已有的网络模型，进而验明了本文提出的设想，即无标度网络中的瞬时同步变化。
关键词：同步；复杂网络；无标度网络；过渡；度分布
绪论
复杂性科学研究兴起于20世纪七八十年代，是用来研究复杂系统和复杂性的一门交叉学科。它研究的复杂系统涉及的范围很广，包括自然、工程、生物、经济、管理、政治与社会等各个方面。它探索的复杂现象小至一个细胞呈现出来的生命现象，大至股票市场的涨落、城市交通的管理、自然灾害的预测，乃至社会的兴衰。
复杂网络广泛存在于自然界和人类社会，是复杂性科学中复杂系统的抽象，网络中的节点是复杂系统中的个体，节点之间的边则是系统中个体之间按照某种规则而自然形成或人为构造的一种关系或相互作用。复杂网络可以用来描述从技术到生物直至社会各类开放复杂系统的骨架，而且是研究它们拓扑结构和动力学性质的有力工具。
复杂网络简而言之即呈现高度复杂性的网络。其复杂性主要表现在以下几个方面：1)结构复杂：表现在节点数目巨大，网络结构呈现多种不同特征。2)网络进化：表现在节点或连接的产生与消失。例如万维网，网页或链接随时可能出现或断开，导致网络结构不断发生变化。3)连接多样性：节点之间的连接权重存在差异，且有可能存在方向性。4)动力学复杂性：节点集可能属于非线性动力学系统，例如节点状态随时间发生复杂变化。5)节点多样性：复杂网络中的节点可以代表任何事物，例如，人际关系构成的复杂网络节点代表单独个体，万维网组成的复杂网络节点可以表示不同网页。 6)多重复杂性融合：即以上多重复杂性相互影响，导致更为难以预料的结果。例如设计一个城市的公交线路网络需要考虑此城市公交线路的演化过程，此演化过程决定网络的拓扑结构。当两个站点之间的人流量越大时，它们之间的连接权重也越大，这时需要调整两个站点间的公交车数量来逐步改善网络性能。
1、复杂网络的发展及研究概况
复杂网络研究传统上属于图论范畴，复杂网络虽然刚刚起步，但受实际网络例如计算机网、社会网的实证研究的激励，复杂网络成为了一个活跃的研究领域。近年来，在高档杂志发表(或者被SCI收录)的复杂网络方向的论文数量呈逐年递增的趋势，有关复杂网络的专题会议也越来越多。
2、复杂网络的发展
追溯图论的发展轨迹，图论的发展主要经历了三个阶段，提出了三类经典的理论模型，包括Euler经典图论、ER随机图以及小世界网络模型和无标度网络模型。
1736年，瑞士数学家Euler考虑了著名的哥尼斯堡七桥问题。他用抽象分析的方法将这个问题转化为图论问题，即把每一块陆地用一个点来表示，将每一座桥用连接相应的两个点的一条线来代替，从而得到一个图。Euler的研究开创了图论这门新的数学分支，成为图论发展的第一个里程碑。此后的两百多年里，现实系统都是用一些规则的网络结构，如一维链、二维平面欧几里得格网、近邻环网等来表示。
20世纪五六十年代，匈牙利两个著名的数学家Erdos和Renyi又一次对图论作出了第二个里程碑式的贡献。他们建立了著名的随机图理论，用相对简单且无明确设计原理的大规模随机图来描述网络，使得边的出现成为概率事件，简称为ER随机图理论。随机图和经典图论之间最大的区别在于引入了随机的方法，使得图的空间变得更大，其数学性质也发生了巨大的变化。由于随机图理论简单而且易于接受，随机图的思想主宰了网络研究长达四十年之久。
由于许多实际网络具有相同的定性性质，且随机图理论不能描述和解释现实的复杂现象。20世纪末，随着计算机技术的高度发展，人们拥有各种网络的数据库，因此对大规模的网络进行实证研究成为了可能。网络科学又一次取得突破性进展，出现了第三个里程碑。美国的Watts和Strogatz发表了题为“小世界网络的群体动力行为”的论文，他们推广了“六度分离”的科学假设，提出了介于规则网络和随机网络之间的小世界网络模型，此模型具有较大的群集系数和较短的平均路径。
小世界特征提出之后，1999年美国的Barabasi和Albert通过实证模拟，发现万维网节点的度分布具有幂指数函数的规律。度用来描述与节点相连的边的数目。在不同的网络中，度所代表的含义也不尽相同。例如，在社会网络中，度可表示个体的作用力和影响程度，一个节点的度越大，表示在整个网络系统组织中的作用和影响就越大，反之亦然。在城市公交网络中，度分布表示城市站点之间的公交线路的多少和重要程度，度越大的站点，其重要性就越大。因为幂指数函数在双对数坐标中是一条直线，这个分布与系统特征长度无关，所以这个特性被称为无标度性质。它反映网络中度分布的不均匀性，只有很少数的节点与其它节点有很多的连接，成为“中心节点”，而大多数节点度很小。针对万维网的动态变化过程，Barabasi等抽象出了一类以均匀增长和线性择优为机制的无标度网络模型(BA模型)，复杂网络的研究由此掀开了新的篇章。
3、复杂网络的研究概况
自小世界性质和无标度特征提出之后，复杂网络的研究取得了许多重要进展。一方面为了发现和刻画实际系统的网络结构，接近现实网络的新的网络模型被不断提出，网络的统计特征逐渐明确，分析方法越来越多，越来越严格。另一方面，为了更深刻的理解复杂系统内部的工作方式和机理，复杂网络上的动力学得到广泛研究，包括网络同步、疾病传播等。
现实网络的统计特征主要包括小世界性质(网络中节点之间的平均距离很短)、无标度性质(网络中节点的度分布向右偏斜，具备幂函数形式)以及群集性或网络传递性等。
无标度性质是现实网络的一个重要特征。BA模型是产生无标度网络的最简单模型。在BA模型中，旧节点得到连线的概率p(k)被假设为与节点的度数k成正比。对于某些实际网络，例如因特网、引文网、美国国立医学图书馆MEDLINE数据库及Los Alamos档案文件库等，p(k)与度数k确实有近似线性关系。但对其它网络如科研合作网络、演员合作网络， 该相互关系是亚线性的。基于此，Krapivsky等提出了非线性择优的网络模型，通过对亚线性、近似线性和超线性择优机制的研究发现，只有近似线性择优能产生无标度网络。同时，由于BA模型初始状态节点的度数均为零，导致择优无法进行，而实际网络中孤立节点被连线的概率是非零的。Dorogovtsev等将线性择优规则修改为带有吸引度的择优，这样，即使初始时刻度数为零的节点也有机会得到连线。然而，新节点选择旧节点连线时，既有择优的可能，又有随机性。基于择优加随机的混合机制，学者们又提出了能在随机网络和无标度网络之间变化的网络模型。
由于BA模型对网络增长只包含一种机制，即增加新的节点并连接到系统中己有节点。而现实网络中，网络是不断演化的。为了更好的吻合现实网络，除了通过改变择优规则，人们还通过节点的重新连线或者增加和删除原有连线来推广BA模型。Bollobas等考虑了允许节点自连线和重复连线的网络模型。Albert和Barabasi研究了包含旧节点间新增连线以及旧边重连的网络模型。Cooper等将BA模型一般化，既考虑增加新节点，又考虑旧节点之间增加新连线的情形。Dorogovtsev和Mendes分析了一类在旧节点间增加连线，同时又以一定概率删除旧边的无向图模型。
针对现实网络节点的有限寿命(如：社会网、引文网)或边的有限容量(如：因特网的路由器或电力网络的节点)，部分学者提出了影响度分布的限制条件。他们指出旧节点得到连线的概率不仅与其度数成正比，而且与其年龄有关，模型假设旧节点逐渐停止连线的过程遵循幂函数规律。
然而，大量事实表明，实际网络中，节点的度及其增长速度并非只取决于年龄Bianconi和Barabasi指出每个节点都有依靠消耗其它节点而竞争获得连线的本能，他们给每个节点定义一个适应能力参数，旧节点得到连线的概率与节点的度数和适应能力成正比。
除了按节点择优连线，Dorogovtsev等提出了一个按边选择节点的简略模型。模型初始为三节点完全图，每个时间步，增加一个新节点并连接到随机选择的一条边的两个端点。按此方式得到的网络模型与BA模型具有相似的结构。
现实网络模型几乎都具有幂率度分布和较大的群集系数，较短的平均路径，而由BA模型演化来的网络模型大都只具有幂率分布，群集系数较小。Holme和Kim，Szabo等在一般的无标度网络模型中引入一个形成三元组的步骤。新节点与某一旧节点连线后，再以一定的概率与被选旧节点的邻居连线，从而达到较大群集系数。
考虑到对诸如世界贸易网之类的网络，人们往往不需要知道全局信息，而只需要了解与自己相关联的信息，李翔和陈关荣提出了局域世界网络模型。新节点加入时，在网络中随机选择M (M为常数)个节点作为新节点的局域世界，新节点与局域世界中的节点择优连线。选取不同的M值，可使得模型的度分布在指数分布和幂率分布之间变化。由于随机选取一部分节点作为新节点的局域世界不符合现实情况，Gomez－Gardenes和Moreno(GM)赋予每个新节点一个参数，此参数用来衡量节点与其它给定节点之间的亲密程度或者几何距离。规定与节点的距离在某范围之内的所有节点作为此节点的邻域世界。通过邻域世界内部的择优连接，生成无标度网络。
与局域世界类似的一个概念是团体。团体是由一系列节点组成的，团体内部连线非常密集而团体之间连线稀疏。团体结构广泛存在于社会网络和生物网络中。团体结构网络除了团体内部的择优连线还有团体之间的择优连线或者新团体的增加。寻找网络中的团体结构也是非常重要的一个内容。在演员合作网和科学家合作网中，如果把一部电影或者一个著作看成任意节点间都相互连接的集团，那么整个合作网的演化过程就是一个个集团的增加过程。集团与集团之间可能通过一些简单的关系相互连接，也可能相互融合。现实网络中很多网络嵌有集团结构。除了团体、集团结构，网络还具有层次性、二分性和非对称性等，例如层次网络，二分网络，非对称性网络。
描述和刻画网络的统计特征逐渐的被发现，求解复杂网络特征参数的方法也越来越多，越来越严格。对于度分布，Barabasi等[6]首先提出了平均场方法，它假设节点的度数为连续变量，通过某一随机选取的节点度数的变化率来求解度分布。Krapivsky等分析度数为k的节点个数的变化率，从而得到率方程，利用大数定理推导模型的度分布。Dorogovtsev等通过讨论节点在某时刻具有度数无的概率，列出主方程，并用Z－变换进行求解。史定华等将复杂网络与马氏链相结合，利用数值模拟的方法得到度分布的数值解。第一个严格求解度分布的方法是Bollobas等提出的。他们利用n划分求解网络中入度为k的节点总数，再利用鞅方法得到网络度分布。
一般情况下，网络中各节点的度是相互关联的，因此节点度的相关性和群集系数也是刻画网络的一个重要统计特征。Newman定义匹配系数来衡量节点度相关性，发现社会网络一般是同类匹配，而技术和生物网络倾向于非同类匹配。Dorogovtsev等定义瞬时联合度分布来衡量相邻节点对的度相关性。瞬时联合度分布的极限存在时，即可得到稳态联合度分布。Krapivsky材和Render利用率方程方法分析了BA模型的度相关性，得到解析表达式。对BA模型以外的其它模型，则很少有解析结果。
复杂网络在多个科学领域，包括自然、社会、工程、生物、经济、政治与管理等各个方面都有广泛应用。常见的网络有社会网络、技术网络、信息网络、生物网络和交通运输网络。社会网络包括朋友关系网、科学引文网、科研合作网、演员网、性关系网, Email网、达尔文和爱因斯坦通信网络、语言网、疾病传播、艾滋病网,世界贸易网]等。技术网络包括因特网、万维网、电力网、移动电话网等。信息网络包括文献索引网络、计算机网络等。生物网络包括氨基酸网络、生态网、蛋白质相互作用网络、神经网络,基因网络、新陈代谢网络、食物链网络[等。交通运输网络包括航空网、城市公共交通网、道路交通网、铁路网、公路网、自然河流网等。
无标度网络的同步转变特性
同步现象是能够在自然界和合成的复杂网络中代表网络群体行为的众多中心现象之一。同步过程描述了一个存在内部互相关系的动态单元的集体的一致动力学现象。Watts和Strogatz通过研究指出，在出现同步现象过程中，存在各单元间的相互影响的网络拓扑结构的重要性。这促使了现代复杂网络结构框架的诞生。从那以后，通过考虑各种网络交互影响的模式，从相位转变逐渐达到同步被广泛地研究。近期的研究结果表明，这些网络的拓扑结构特点在很大程度上影响了临界耦合强度值，——同步现象的起始值，和完全同步状态的稳定性。作为例子，无标度网络被给予了特别的关注，这是因为它是许多复杂网络的主干骨。然而，基础网络的拓扑特性并不会影响同步相位转变的阶数，因为它们的二阶特性保持不变。
自从在随机网络和无标度网络中发现了一个突变过渡后，对复杂网络中相位瞬变研究最近得到了众多关注。对于一群孤立的节点，当对其随机地加边时，一些相互连接的小群体将会出现，实验证明，这些变化一般都是一个连续的过程，即它们是一个二阶过渡。然而，当我们改变加边规则后，例如遵循PR规则——著名的Achlioptas增长过程，试验结果为一个不连续的过程，即一个一阶过渡。这些现象的发现为往后的复杂网络特性的研究提供了指导性作用。然而，一些关于这种现象的微观机制以及可能存在于其他背景下的疑问仍然没有得到解决。基于此出发点，我们推测当网络的局部不均匀结构和它本身的动态特性存在一个有益的关系时，这种动态突变就会出现。在本文中，我们在Kuramoto振子同步的背景下验证了这个推测。当振子的特征频率与它们的度存在有益关系时，我们得到了瞬时同步现象。进一步，我们解析地分析了星形网络中的这种一阶转变，并指出网络的不均匀性和上面的这种关系是这种变化的主要因素。
我们先考虑一个含有N个耦合振子的无权无向网络。每个振子的相位，用，根据Kuramoto模型随时间变化：
（1）
其中i=1，…，N这里的表示振子i的特征频率。振子间的关系用网络的关联矩阵A表示，当振子i和振子j连接时，其他情况。参数入是相互关联的节点的耦合强度。
最初的Kuramoto模型假设振子间是完全相连的，即。在这种情况下，当耦合强度大于临界值时，同步状态，即，就会出现。为了观察随着的增长而引起的变化，我们将通过下面公式在N个振子中计算同步的程度：
（2）
上面序参数的系数，，衡量集团行为的一致性，当系统完全同步时，当完全不同步时。另外，的值是系统集团动态的平均相位。典型的，作为的函数，的平均值是一个从到的二阶相位转变，它有一个临界耦合值，这里是特征频率的分布函数，，它是单峰对称的。
这里我们将在全局同步范围内着重于局部水平上动态特性和拓扑特性的影响。特别地，我们将通过每个节点的内部频率来直接分辨出它的度，所以在方程中。注意，这里是的，但反之不一定成立。为了研究动态特性和结构特性关系的影响，我们建立的一组网络来模拟Kuramoto模型。这个模型让我们能通过调整一个参数来建立一些具有相同平均连接度<k>的的网络，这些模型是从ER模型到BA无标度模型的中间模型。对于，可以得到一个度具有Poisson分布的随机模型，对于，则是一个无标度模型，其。的中间值是调整网络的不均匀性的，且从到，不均匀性逐步增加。在图一中的四个图，我们得到了这四个网络的同步图表。极限例子是ER和BA网络，分别对应于图6的（a）和（d）。网络的大小是，连接度<k>=6。

图1不同网络的同步图表
每个图中的值分别为(a)(ER)，(b)，(c)，(d) (BA)，图中画出了对前向连续和后向连续，间隔为。网络的大小是，连接度<k>=6。
对于图1中的每个模型都计算了两个同步图表，，标为前向和后向连续。前面一个是通过逐渐增加入的值，并在点画出相应的序参数r的静态值。后向连续则是从到逐渐减小的的值。图中(a)到(c)的前向和后向同步图表非常吻合，这说明它们都是二阶转变。
对于BA模型的结果令人感到意外，在此模型中出现了一个尖锐的一阶转变。在前向图表中，序参数一直时，直到达到同步起始值时，r值突变，，这说明所以网络几乎在同一瞬间达到同步状态。同样，后向连续也有一个类似的从完全同步到完全不同步的突变。这两个突变发生在不同的r值处，这说明整个的同步图表表现出一个迟滞现象。
为了深入研究同步转变的序参数的变化，在前向连续中计算出有效频率，如下公式：
（3）
其中。另外，在一类度K的范围内通过平均个有相同度的节点来计算的变化，
(4)
从图2中我们可以看到个体的频率和不同曲线逐渐趋于系统的平均频率W=<k>=6，一直到完全同步。图2中(a)（ER模型）表明那些度大的节点先到达平均频率W，度数小的点后到达。随着网络不均匀性的增加[分别看图（b）和（c），它们对应的和]，在趋近过程中它们的差别逐渐减小。最终，对于BA模型，节点在被锁定前都各自保持自己的频率，直到瞬间突变，如（d）所示。因此，BA网络中的一阶突变表明在没有达到耦合临界值之前，没有出现任何节点同步的信号。
为了进一步探究具有无标度性质网络中相应的瞬时同步现象，在图3中画出了不同的，不相干且具有不同度分布指数的无标度网络的同步图表。它们添加了具有度指数为的度分布，。同步图表是根据前向连续得到的，从的位置开始，步长的绝对增量为。对于每个值，Kuramoto模型的动态量一直在变化，直到r值达到静态。从图可清楚地知道一阶同步变化对于所有研究的值度存在，这种现象表明在SF网络中瞬时同步现象普遍存在。另外，从图中可观察到同步的起始值在随的减小而逐渐增大。

图2
上图为图1中的网络模型在前向连续过程中，其节点有效频率随耦合强度的变化曲线图。图中有色点为各个节点的频率值，而实线表明节点的有效频率的平均值具有相同的度。

图3
图8图示为通过模型建立的几种SF网络的同步图表，所有网络都有一个度分布，它们的指数分别为，网络规模为。连续增长的步长为。
在本章中，我们证实了当节点的网络拓扑结构和自身的特征频率（动态特性）之间存在一个积极的关系时，无标度网络中的同步转变将是一个一阶转变，即表现为一个不连续过程。进一步，根据本文的结果，我们可推测这种转变的出现是由于拓扑特性和动态特性内在的相互影响而产生的，而不是因为各节点的特征频率的分布特性所决定的。
- 9 -