复杂网络演化模型研究

答辩人:陶少华指导老师:刘玉华教授复杂网络演化模型研究及拓扑结构优化提纲1.复杂网络概述2.自相似性复杂网络模型的建立3.自相似网络模型测量方法的深入讨论4.基于吸引因子的网络模型的建立5.无尺度网络拓扑结构优化的研究6.结论与展望7.参考文献8.参加课题、发表文章1.复杂网络概述1960年，提出了随机网络（ER）模型.1998年，提出了小世界网络模型。1999年，提出了无尺度模型。随后又提出了许多BA的扩展模型。2.自相似性复杂网络演化模型的建立自相似性网络的形成是根据节点之间的信息传递性，节点之间传递的信息有共同或相似性，则建立连接。如社会中人们之间的交往。节点传递信息，最终形成网络的自相似性质。社会网络中，如“物以类聚，人以群分”。模型生成算法可以描述为如下过程：节点对自身有认知，向其周围节点传递信息，如果节点彼此之间传递的信息具有相同或相似性，则建立连接。网络中加入新节点新节点与老节点彼此向对方传递信息，有相似之处则连接。12,,...,pppmpeeev12(,,...,)qqqmqveee如果节点的m个属性与节点的m个属性有相似的信息则表示为：。相似连接，与节点连接的概率依赖于相似的程度，连接概率服从如下的规则。12(,,...,)qqqmqveee12,,...,pppmpeeev~qipieepvqv1,()mpqiipqc信息传递模型表示节点对在第i个属性下的相似度（即相似的程度）1,()mpqiipqc()pqic,pqvv假设每个节点v有m个属性,表示节点对在第i个属性下的相似程度。推导过程如下：模型的数学验证()pqic,pqvv由上述模型可知，在t时刻，网络的节点数为N，则f(N)可表示为：111()2NNmpqipqiqpfNc每隔一个时间段网络就增加新节点，即节点总数增加一个单位，f在由时间h分隔的相互间的自相关函数则自相关函数满足:0limTTrhfthfftfdt20cDrhrch仿真结果本文分别以网络节点100、500、1000与1500时形成的网络为例。3.自相似网络模型测量方法的深入讨论节点的分布具有不均匀性。为了能够客观的反映每个盒子中覆盖的节点数，用信息维数进行测量。对容量维数进行如下改进：对每个覆盖盒子按填充程度进行编号;统计出分形结构落入第i只盒子的概率Pi(r)：得出信息公式信息维数公式iiNrprNr1logNriiriIrprp0lim1logirIrDr仿真结果以节点数100、500、1000为例：4.吸引因子存在的网络模型问题的提出BA模型预测全部的节点随着时间的增长增加他们的连接数量。许多实例表明在真实系统中一个节点的连接与增长率并不仅仅是依赖节点进入网络的长短。基于吸引因子演化网络模型的建立网络增长，在每一个时间步里，具有吸引因子的新节点被加进来。新节点与老节点相连的概率依赖于与，规则如下：ikijjjiiikk)(模型参数的讨论当大，也大时，这时这种节点在与新节点相连时就有很大的优势。当大，小时，这就相当于一个老节点日趋衰落，没有太大的优势。当小，大时，这种情况下对新节点很有利。ikikiikiiki仿真结果吸引因子模型与BA模型，度与度分布的比较：5.无尺度网络模型拓扑结构优化研究具有很强的鲁棒性。同时也有脆弱性。改变无尺度网络集散节点的拓扑结构，以增强网络的抗协同攻击能力。层次式处理与分布式处理层次式处理建立节点度数统计表,在网络中当每一个节点的连接数达到一个阈值,就认为该节点是集散节点.此时如果还有新的要连接，则建立虚拟节点，其后新进的节点粘贴到虚拟节点上。依此类推，在逻辑上形成虚拟节点的层次结构，以层二叉树为例。如果一个节点出了故障，由父节点或子节点或同一层相邻节点来代替它。每次要连接时，对层次结构从上到下进行遍历，搜索度数小于R的虚拟节点，一旦找到，则粘贴到这个节点上。模型的控制算法如下：增长性：假设网络最初有个节点，当加入一个新节点时，新节点通过条新加入的边与网络中已有的个节点相连。优先粘贴:粘贴概率服从如下规则0m0()mmmiijjkqk约束控制：节点的最大度若，则生成新的虚拟节点。节点遍历：如果有新涌现的节点与老节点相连，则遍历与其下层的虚拟节点，找到其中第一个度数值小于的节点与之相连。maxkRmaxkR分布式处理集散节点除控制为层次结构外，还可以控制为分布式处理。超立方体结构是分布式系统中的一种结构,以三维立方体为例，将网络拓扑结构生成为一个三维立方体.过程如下：生成7个虚拟节点，与原有的一个节点组成三维立方体结构的8个顶点。每一节点均与相邻的三个节点相连结。相互连结的节点，必须遵循如下原则：两两相连的节点当且仅当和的二进制编码有一位不同。对节点的度数设定一个阈值，超过这个值，新节点则连接到它相邻的节点上。由于立方体结构节点之间信息互通每个节点连接的数远小于集散节点的连接数，因此当其中一个节点出现故障时，不影响整个系统的运行.可扩展为n维立方体结构。仿真结果原有集散节点结构层次式结构立方体结构：经过控制的集散节点形成层次结构或超立方体结构的度分布较均匀，并且当某个节点出了故障可以由其它节点迅速的代理它。与集散节点相比较层次结构与立方体结构具有很强的稳健性与鲁棒性。6.结论创新点：1.利用节点之间信息传递的方式，提出了自相似性的复杂网络模型。2.分析了容量维数的不足，并用信息维数方法，对自相似网络的测量进行了深入讨论。3.根据每个节点内在具有的吸引力，提出了基于吸引因子的复杂网络模型。4.对无尺度网络模型的拓扑结构的优化进行了研究，提出了采用层次式与分布式处理，增强了网络的稳健性。展望自相似性还有待深入讨论吸引因子的变化规律还有待研究参考文献[1]祁国宁，徐福缘，王怛山，复杂网络-系统结构研究文集，浙江大学现代制造工程研究所。[2]ErdòsP.andRényA.,Ontheevolutionofrandomgraphs,PublicationoftheMathematicalInstituteoftheHungarianAcademyofScience5,1960,pp.17~61.[3]WattsD.J.andStrogatzS.H.,Collectivedynamicsofsmall-worldnetworks,Nature393,1998,pp.440~442.[4]Barabasi,A.-L.&Albertr,Emergenceofscalinginrandomnetworks.Science,1999.[5]Albert-Laszlo,BarabasiandEricBonaber,Scale-FreeNetworks,ScientiAmerican5.2003:pp.50~59.[6]SolomonoffR.andRapoportA.,Connectivityofrandomnets,BulletinofMath.Biophys.13,1951,pp.107~117.[7]NewmanaM.E.J.andWattsD.J.,Reormalizationgroupanalysisofthesmall-worldnetworkmodel,Phys.Lett.A263,1999,pp.341~346.[8]AlbertR.,JeongH.,andBarabásiA.-L.,Diameteroftheworld-wideweb,Nature401,1999,pp.130~131.[9]BarabásiA.-L.,AlbertR.,andJeongH.,Mean-fieldtheoryforscale-freerandomnetworks,PyhsicaA272,1999,pp.173~187.[10]DorogovtsevS.N.andMendesJ.F.F.,Effectoftheacceleratinggrowthofcommunicationnetworksontheirstructure,Phys.Rev.E63,2001,025101.[11]JeongH.,NdaZ.,andBarabásiA.-L.,Measuringpreferentialattachmentinevolvingnetworks,Europhys.Lett.61,2003,pp.567~572.[12]LiuZ.H.,etal.,Connectivedistributionandattacktoleranceofgeneralnetworkswithbothpreferentialandrandomattachments,PhysicsLettersA303,2002,pp.337~344.[13]KrapivskyP.L.,RednerS.,andLeyvrazF.,Connectivityofgrowingrandomnetworks,Phys.Rev.Lett.85,2000,pp.5234~5237.[14]ShiD.H.,ChenQ.H.,andLiuL.M.,Markovchain-basednumericalmethodfordegreedistributionofgrowingnetworks,Phys.Rev.E71,2005,036140.[15]AlbertR.andBarabásiA.-L.,Topologyofevolvingnetworks:localeventsanduniversity,Phys.Rev.Lett.85,2000,pp.5234~5237.[16]ShiD.H.,LiuL.M.,ZhuX.,andZhouH.J.,Degreedistributionsofevolvingnetworks,Europhys.Letts.76(4),2006,1035-2.[17]KlemmK.andEguiluz,V.M.,Growingscale-freenetworkswithsmall-worldbehavior,Phys.Rev.E65,2002,051702.[18]Cladarellg,Capoccl.A,Delosrios.P,etal,Scale-FreeNetworksfromVaryingVertexIntrinsicFitness,Phys.Rev.Lett,2002.[19]YuhuaLiu,JiweiCao.etc,“ASelf-organizationInternetTopolotyModelBasedonMessegeTransfer”,DCDIS,2006,pp15-18,[20]谢和平，张永平，分形几何，重庆大学出版社，1990.[21]王世俊，关于Weierstress函数图像K-维函数的证明。[22]汪富泉、李后强，分形几何与动力系统,中国科学技术大学出版社1993,O157/52.[23]Vicsek,T.FractalGrowthPhenomena,2nded.,PartIV,WorldScienti_c,Singapore,1992.[24]Feder,J.Fractals(PlenumPress,NewYork),1988.[25]Xenarios,I.etal.DIP:thedatabaseofinteractingproteins.NucleicAcidsRes.28,pp.289-291,2000.[26]DatabaseofInteractingProteins(DIP).[27]S.N.DorogovtsevandJ.F.F.Mendes,Evolutionofnetworkswithagingofsites,Phys.Rev.E62,2000,1842.[28]Q.Chen,H.Chang,R.Govindan,S