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