复杂网络入门及级联失效

《复杂网络入门及级联失效》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、小世界网络StevenH.Strogatz的文章Exploringcomplexnetworks综述了动力学网络方面的研究。他把网络分成规则网络和复杂网络两种，而复杂网络分为随机网络，小世界网络和自相似网络。小世界网络和自相似网络都介于规则和随机网络之间。简介在数学、物理学和社会学中，小世界网络是一种数学之图的类型，在这种图中大部分的结点不与彼此邻接，但大部分结点可以从任一其他点经少数几步就可到达。若将一个小世界网络中的点代表一个人，而连结线代表人与人认识，则这小世界网络可以反映陌生人由彼此共同认识的人而连结的小世界现象。

2、自相似指的是这样一种性质，系统在不同尺度上看起来性质相同。小世界网络的定义就没有这么明确，只说它是规则和随机网络的中间物。这种不明确性可能来源于对它了解的缺乏。衡量网络的特征在考虑网络特征的时候，使用两个特征来衡量网络：特征路径长度（characteristicpathlength）：在网络中，任选两个节点，连通这两个节点的最少边数，定义为这两个节点的路径长度，网络中所有节点对的路径长度的平均值，定义为网络的特征路径长度。这是网络的全局特征。聚合系数(clusteringcoefficient)：假设某个节点有k条边，则这

3、k条边连接的节点（k个）之间最多可能存在的边的条数为k(k-1)/2，用实际存在的边数除以最多可能存在的边数得到的分数值，定义为这个节点的聚合系数。所有节点的聚合系数的均值定义为网络的聚合系数。聚合系数是网络的局部特征，反映了相邻两个人之间朋友圈子的重合度，即该节点的朋友之间也是朋友的程度。应用解释对于规则网络，任意两个点（个体）之间的特征路径长度长（通过多少个体联系在一起），但聚合系数高（你是朋友的朋友的朋友的几率高）。对于随机网络，任意两个点之间的特征路径长度短，但聚合系数低。而小世界网络，点之间特征路径长度小，接近随

4、机网络，而聚合系数依旧相当高，接近规则网络。发现规则网络具有很高的聚合系数，大世界（largeworld，意思是特征路径长度很大），其特征路径长度随着n(网络中节点的数量)线性增长，而随机网络聚合系数很小，小世界（smallworld，意思是特征路径长度小），其特征路径长度随着log(n)增长中说明，在从规则网络向随机网络转换的过程中，实际上特征路径长度和聚合系数都会下降，到变成随机网络的时候，减少到最少。但这并不是说大的聚合系数一定伴随着大的路径长度，而小的路径长度伴随着小的聚合系数，小世界网络就具有大的聚合系数，而特征

5、路径长度很小。试验表明，少量的shortcut的建立能够迅速减少特征路径长度，而聚合系数变化却不大，因为某一个shortcut的建立，不仅影响到所连接的节点的特征路径长度，而且影响到他们邻居的路径长度，而对整个网络的聚合系数影响不大。这样，少量的shortcut的建立就能使整个网络不知不觉地变成小世界网络。实际的社会、生态、等网络都是小世界网络，在这样的系统里，信息传递速度快，并且少量改变几个连接，就可以剧烈地改变网络的性能，如对已存在的网络进行调整，如蜂窝电话网，改动很少几条线路，就可以显著提高性能。网络科学简单的说,网

6、络科学（NetworkScience）应该是专门研究复杂网络系统的定性和定量规律的一门崭新的交叉科学,研究涉及到复杂网络的各种拓扑结构及其性质,与动力学特性(或功能)之间相互关系,包括时空斑图的涌现、动力学同步及其产生机制,网络上各种动力学行为和信息的传播、预测(搜索)与控制,以及工程实际所需的网络设计原理及其应用研究,其交叉研究内容十分广泛而丰富。发展简史图论和拓扑学网络科学首先得益于图论和拓扑学等应用数学的发展。关于图论的文字记载最早出现在欧拉1736年的论著中,他所考虑的原始问题具有很强的实际背景。在数学上,关于哥尼

7、斯堡七桥问题、多面体的欧拉定理、四色问题等都是拓扑学发展史的重要问题。而在欧拉身后，一些数学大师如柯西、汉密尔顿、凯利、基尔霍夫、波利亚等都对图论作出了贡献，使这门科学得到了快速的发展。1、哥尼斯堡七桥问题[2] 哥尼斯堡是东普鲁士的首都,今俄罗斯加里宁格勒市,普莱格尔河横贯其中。18世纪在这条河上建有七座桥,将河中间的两个岛和河岸连结起来。人们闲暇时经常在这上边散步,有人提出:能不能每座桥都只走一遍,最后又回到原来的位置。这个看起来很简单却很有趣的问题吸引了大家,很多人在尝试各种各样的走法,然而无数次的尝试都没有成功。谁

8、也没有做到,看来要得到一个明确、理想的答案决非那么容易。1736年,有人带着这个问题找到了当时的大数学家欧拉,欧拉经过一番思考,很快就用一种独特的方法给出了解答。欧拉首先把这个问题简化,他把两座小岛和河的两岸分别看作四个点,而把七座桥看作这四个点之间的连线.欧拉图的研究开创了“图论”这门新的数学分支[7