基于自相似性的复杂网络

基于自相似性的复杂网络报告人:陶少华2005年10月引言复杂网络模型简介自相似性复杂网络结论1引言1960年数学家Erdos和Renyi提出了随机图理论，研究复杂网络中随机的拓扑模型，自此ER模型一直是研究复杂网络的基本模型。但是，近年来研究发现，测量现实网络的实际数据得到的许多实验结果与随机图模型并不符合，因此需要新的网络模型更合理的描述实际网络的特性。Watts和Strgatz提出了小世界（WS）模型，刻画了实际的网络所兼有的大的聚簇和短的平均路径距离的特性，然而现实世界中的网络还被发现极少数结点具有大量的连结而众多的结点仅有少量连结，这同样无法用随机图模型加以合理解释。因此，Barabasi和Albert提出了无尺度模型，所生成的复杂网络的度分布是幂律分布，，为网络中一个节点连结其它节点的边的条数。BA网络模型指出了决定互联网、万维网等网络具有无尺度模型的两个基本原理：增长性和择优连结。。但它仍然具有一定的局限性，在现实在各种复杂网络常常具有一些非幂律特征，如指数中止、小变量饱和等。为了在微观层面更深入的研究复杂网络的拓扑结构和演化的规律，研究人员作了大量新的尝试和努力，对网络的演化已经有了长足的进展，已经研究的演化因素包括各种类型的择优连结、局域世界、适应度、竞争等等。具体来说，Bianconi与Barabasi提出了适应度模型，并首先研究了竞争因素的影响。李翔与陈关荣则提出了局域世界演化网络模型，他们认为局域性存在择扰连结在而对于全局并不适用。尽管众多的网络演化模型已经被用来分析和研究可能潜藏的演化规律，但这些研究工作仍然忽视了一些重要的因素。如计算机网络节点之间的连结，如果是按照择优连结概率，则新的节点会全部连结到一个节点，但现实网络并非如此，而是形成不同的集散节点。这个例子说明了网络节点之间的连结有可能共性才相连，因此建立并研究基于相似性的网络演化模型有利于我们更好地认识现实中的复杂网络。2复杂网络模型简介复杂网络就是具有复杂拓扑结构和动力行为的大规模网络，它是由大量的节点通过边的相互连结而构成的图。根据不同的拓扑结构复杂网络可以分为规则网络，随机网络，小世界网络，无尺度网络等等。2.1小世界网络模型1998年，Watts和Strogatz提出了小世界网络模型。这个模型介于规则网络和随机网络之间并在他们之间起桥梁作用。建立网络模型步骤如下：初始化：从具有个节点的环形网络开始，其中每一节点都与它初始的个邻居相连（在每一边有个邻居）。N2kk随机化：以概率随机为规则网络的每条边重新连线，同时保证没有自连结和重连边，这一过程引进条长距离捷径（重新连结的边）边，它们连结那些拥有不同邻居的部分节点。当=0时，对就的为网络规则图，当时，对应的为随机网络图，当介于（0,1）区间任意值时，模型显示出小世界特性。小世界网络的主要特点：ppNKp1pp度分布为指数分布且峰值取平均值，每个节点有大致相同数目的连结数，平均路径短且聚集系数大如图，其中为平均路径，为聚集系数。小世界网络介于规则网络和随机网络之间，它实现了从规则到完全随机之间的连续演变。LC2.2无尺度网络模型1999年，Barabasi和Albert提出了无尺度网络模型，它通过增加新的节点而实现连续增长，同时这些新的节点总是倾向于选择连结已经具有大量连结的节点。BA模型具体描述如下：增长性：假设网络最初有个节点。每一次加入一个新节点，每次加入的新节点通过条新加入的连结边与网络中已有的0m0()mm个节点相连。优先连结：我们假设每个新节点与节点相连的概率都依赖于节点的度，并且这个概率服从如下的规则：根据上述步骤重复次后得到一个有个节点和条边的网络。miikiikiijjkkkt0Ntmmt在1999年.Barabási,与Albert用数量模拟表明具有k条边的节点的概率服从指数为r=3的幂律分布，如图3：无尺度网络的主要特点为度分布为幂律分布，极少数节点有大量的连结，而大多数节点只有很少的连结。同时，无尺度还具有某些重要特性，可以承受意外的故障，但对恶意攻击却很脆弱。3自相似性复杂网络网络通过节点与节点相连成形成，节点与节点之间是通过某种共性而连在一起。如人际关系之中的“物以群聚，人以类分”。3.1自相似性网络模型1975年美国数学系教授曼德布罗特首次提出了“分形”这个概念，其原意是“不规则的、分数的、支离破碎的”物体，我们把具有某种方式的自相似性的图形或集合称为分形。自相似性就是局部与整体相似，局部中又有相似的局部，每一小局部中包含的细节并不比整体所包含的少，不断重复的无穷嵌套，形成了奇妙的分形图案，它不但包括严格的几何相似性，而且包括通过大量的统计而呈现出的自相似性。我们利用分形的思想来测量复杂网络的自相似性。自相似性的系数在某个范围内波动,有最大标度和最小标度。本文采用复杂网络的三大统计属性平均最短路径长度、集群系数、顶点度分布作为自相似性复杂网络的演化依据。假设一个包含个节点的网络，是网络中节点之间的平均最短距离。nl1112ijijldnn其中，是从节点到节点的最短距离。集群系数是网络的另一个重要的统计属性。可用如下公式量化：这里为节点的局部集群系数。的计算公式为：ijd1iicnciCiiC21iiiiECkk对于网络节点，它通过条边与其它个网络节点（邻居）相连结。如果这个邻居是群的一部分，则在它们之间有条边连结。个邻居之间实际有的边数与总边数之比就给出了节点的集群系数。除平均最短路径长度及集群系数外，网络还有一个重要的统计属性就是顶点度分布。顶点度分布用分布函数来表示也就是网络中度数为的顶点的个数占顶点总个数的比例。iikikik12iikkikiE12iikkiiCpk找一个实际的网络图，测量一下局部图形的平均最短路径长度，集群系数与顶点度分布。然后再就整个的图测量一下三个统计值。因为网络是动态增长的，为了测量一下当网络增长之后是否具有相似性，当网络任意增长到一定的程度时，再测量一下这三个统计值。用得到的实际数据画出它的仿真图，如果在大致范围内局部图形、整个图形以及增长的网络图形的最短路径长度、集群系数、顶点度分布的仿真图形趋于一致，那么我们得出的结论就是复杂网络具有自相似性。