《复杂网络演化模型研究.ppt》由会员分享，可在线阅读，更多相关《复杂网络演化模型研究.ppt（36页珍藏版）》请在三一办公上搜索。
1、答 辩 人:陶少华 指导老师:刘玉华 教授,复杂网络演化模型研究及拓扑结构优化,提纲,1.复杂网络概述2.自相似性复杂网络模型的建立3.自相似网络模型测量方法的深入讨论4.基于吸引因子的网络模型的建立5.无尺度网络拓扑结构优化的研究6.结论与展望7.参考文献8.参加课题、发表文章,1.复杂网络概述,1960年，提出了随机网络（ER）模型.1998年，提出了小世界网络模型。1999年，提出了无尺度模型。随后又提出了许多BA的扩展模型。,2.自相似性复杂网络 演化模型的建立,自相似性网络的形成是根据节点之间的信息传递性，节点之间传递的信息有共同或相似性，则建立连接。如社会中人们之间的交往。节点传递
2、信息，最终形成网络的自相似性质。社会网络中，如“物以类聚，人以群分”。模型生成算法可以描述为如下过程：,节点 对自身有认知，向其周围节点传递信息，如果节点彼此之间传递的信息具有相同或相似性，则建立连接。网络中加入新节点 新节点与老节点彼此向对方传递信息，有相似之处则连接。,如果节点 的m个属性与节点 的m个属性有相似的信息则表示为：。相似连接，与节点 连接的概率依赖于相似的程度，连接概率服从如下的规则。,信息传递模型 表示节点对 在第i个属性下的相似度（即相似的程度）,假设每个节点v有m个属性,表示节点对 在第i个属性下的相似程度。推导过程如下：,模型的数学验证,由上述模型可知，在t时刻，网络
3、的节点数为N，则f(N)可表示为：,每隔一个时间段网络就增加新节点，即节点总数增加一个单位，f在由时间h分隔的相互间的自相关函数则自相关函数满足:,仿真结果,本文分别以网络节点100、500、1000与1500时形成的网络为例。,3.自相似网络模型测量 方法的深入讨论,节点的分布具有不均匀性。为了能够客观的反映每个盒子中覆盖的节点数，用信息维数进行测量。对容量维数进行如下改进：,对每个覆盖盒子按填充程度进行编号;统计出分形结构落入第 i 只盒子的概率Pi(r)：得出信息公式 信息维数公式,仿真结果,以节点数100、500、1000为例：,4.吸引因子存在的网络模型问题的提出,BA模型预测全部的
4、节点随着时间的增长增加他们的连接数量。许多实例表明在真实系统中一个节点的连接与增长率并不仅仅是依赖节点进入网络的长短。,基于吸引因子演化网络模型的建立,网络增长，在每一个时间步里，具有吸引因子的新节点被加进来。新节点与老节点相连的概率依赖于 与，规则如下：,模型参数的讨论,当 大，也大时，这时这种节点在与新节点相连时就有很大的优势。当 大，小时，这就相当于一个老节点日趋衰落，没有太大的优势。当 小，大时，这种情况下对新节点很有利。,仿真结果,吸引因子模型与BA模型，度与度分布的比较：,5.无尺度网络模型拓扑结构优化研究,具有很强的鲁棒性。同时也有脆弱性。改变无尺度网络集散节点的拓扑结构，以增强
5、网络的抗协同 攻击能力。层次式处理与分布式处理,层次式处理,建立节点度数统计表,在网络中当每一个节点的连接数达到一个阈值,就认为该节点是集散节点.此时如果还有新的要连接，则建立虚拟节点，其后新进的节点粘贴到虚拟节点上。依此类推，在逻辑上形成虚拟节点的层次结构，以层二叉树为例。,如果一个节点出了故障，由父节点或子节点或同一层相邻节点来代替它。每次要连接时，对层次结构从上到下进行遍历，搜索度数小于R的虚拟节点，一旦找到，则粘贴到这个节点上。模型的控制算法如下：,增长性：假设网络最初有个 节点，当加入一个新节点时，新节点通过 条新加入的边与网络中已有的 个节点相连。优先粘贴:粘贴概率服从如下规则,约
6、束控制：节点的最大度 若，则生成新的虚拟节点。节点遍历：如果有新涌现的节点与老节点相连，则遍历与其下层的虚拟节点，找到其中第一个度数值小于的节点与之相连。,分布式处理,集散节点除控制为层次结构外，还可以控制为分布式处理。超立方体结构是分布式系统中的一种结构,以三维立方体为例，将网络拓扑结构生成为一个三维立方体.过程如下：,生成7个虚拟节点，与原有的一个节点组成三维立方体结构的8个顶点。每一节点均与相邻的三个节点相连结。相互连结的节点，必须遵循如下原则：两两相连的节点当且仅当和 的二进制编码有一位不同。对节点的度数设定一个阈值，超过这个值，新节点则连接到它相邻的节点上。,由于立方体结构节点之间信
7、息互通每个节点连接的数远小于集散节点的连接数，因此当其中一个节点出现故障时，不影响整个系统的运行.可扩展为n维立方体结构。,仿真结果,原有集散节点结构,层次式结构,立方体结构：,经过控制的集散节点形成层次结构或超立方体结构的度分布较均匀，并且当某个节点出了故障可以由其它节点迅速的代理它。与集散节点相比较层次结构与立方体结构具有很强的稳健性与鲁棒性。,6.结论,创新点：1.利用节点之间信息传递的方式，提出了自相似性的复杂网络模型。2.分析了容量维数的不足，并用信息维数方法，对自相似网络的测量进行了深入讨论。3.根据每个节点内在具有的吸引力，提出了基于吸引因子的复杂网络模型。4.对无尺度网络模型的
8、拓扑结构的优化进行了研究，提出了采用层次式与分布式处理，增强了网络的稳健性。,展望,自相似性还有待深入讨论吸引因子的变化规律还有待研究,参考文献,1 祁国宁，徐福缘，王怛山，复杂网络-系统结构研究文集，浙江大学现代制造工程研究所。2 Erds P.and Rny A.,On the evolution of random graphs,Publication of the Mathematical Institute of the Hungarian Academy of Science 5,1960,pp.1761.3 Watts Strogatz S.H.,Collective dynam
9、ics of small-world networks,Nature 393,1998,pp.440442.4 Barabasi,A.-L.&Albertr,Emergence of scaling in random networks.Science,1999.5Albert-Laszlo,Barabasi and Eric Bonaber,Scale-Free Networks,Scienti American 5.2003:pp.5059.6 Solomonoff R.and Rapoport A.,Connectivity of random nets,Bulletin of Math
10、.Biophys.13,1951,pp.107117.7 Newmana M.E.J.and Watts D.J.,Reormalization group analysis of the small-world network model,Phys.Lett.A 263,1999,pp.341346.8 Albert R.,Jeong H.,and Barabsi A.-L.,Diameter of the world-wide web,Nature 401,1999,pp.130131.9 Barabsi A.-L.,Albert R.,and Jeong H.,Mean-field th
11、eory for scale-free random networks,Pyhsica A 272,1999,pp.173187.10 Dorogovtsev S.N.and Mendes J.F.F.,Effect of the accelerating growth of communication networks on their structure,Phys.Rev.E63,2001,025101.11 Jeong H.,Nda Z.,and Barabsi A.-L.,Measuring preferential attachment in evolving networks,Eu
12、rophys.Lett.61,2003,pp.567572.12 Liu Z.H.,et al.,Connective distribution and attack tolerance of general networks with both preferential and random attachments,Physics Letters A 303,2002,pp.337344.13 Krapivsky P.L.,Redner S.,and Leyvraz F.,Connectivity of growing random networks,Phys.Rev.Lett.85,200
13、0,pp.52345237.14 Shi D.H.,Chen Q.H.,and Liu L.M.,Markov chain-based numerical method for degree distribution of growing networks,Phys.Rev.E71,2005,036140.15 Albert R.and Barabsi A.-L.,Topology of evolving networks:local events and university,Phys.Rev.Lett.85,2000,pp.52345237.,16 Shi D.H.,Liu L.M.,Zh
14、u X.,and Zhou H.J.,Degree distributions of evolving networks,Europhys.Letts.76(4),2006,1035-2.17 Klemm K.and Eguiluz,V.M.,Growing scale-free networks with small-world behavior,Phys.Rev.E65,2002,051702.18 Cladarellg,Capoccl.A,De los rios.P,et al,Scale-Free Networks from Varying Vertex Intrinsic Fitne
15、ss,Phys.Rev.Lett,2002.19 Yuhua Liu,Jiwei Cao.etc,“A Self-organization Internet Topoloty Model Based on Messege Transfer”,DCDIS,2006,pp 15-18,20 谢和平，张永平，分形几何，重庆大学出版社，1990.21 王世俊，关于Weierstress函数图像K-维函数的证明。22 汪富泉、李后强，分形几何与动力系统,中国科学技术大学出版社 1993,O157/52.23 Vicsek,T.Fractal Growth Phenomena,2nd ed.,Part I
16、V,World Scienti_c,Singapore,1992.24 Feder,J.Fractals(Plenum Press,New York),1988.25 Xenarios,I.et al.DIP:the database of interacting proteins.Nucleic Acids Res.28,pp.289-291,2000.26 Database of Interacting Proteins(DIP).27 S.N.Dorogovtsev and J.F.F.Mendes,Evolution of networks with aging of sites,Ph
17、ys.Rev.E 62,2000,1842.28 Q.Chen,H.Chang,R.Govindan,S.Jamin,S.Shenker and W.Willinger,The origins of power laws in Internet topologies revisited.Proc.IEEE INFOCOM,2002.29 S.N.Dorogovtsev and J.F.F.Mendes,Scaling behaviour of developing and decaying networks,Europhys.Lett.52.2000.30 Xiang Li and Guanr
18、ong Chen,A local-world evolving network model,physica A.328.2003,pp.274-286.31 Ginestra Bianconi and Albert-Laszlo Barabasi,Competition and multiscaling in evolving networks,2000.,参加的课题,重叠网络避免集散节点形成的拓扑控 制，国家自然科学基金，编号：60673163，2007-2009。网络优化算法研究，横向课题基金，编号：233010，2004-2005。,发表的论文,1.Yuhua Liu,Shaohua T
19、ao,Kaihua Xu,Demao Tan,“The Strategies against Vulnerability of Hubs in Complex Networks”.The 3th International Conference on Impulsive Dynamical Systems and Applications,Published by the journal of Dynamics of Continuous,Discrete and Impulsive Systems(DCDIS),Qindao,China,21-23 July 2006.(SCI/ISTP)收
20、录.2.Yuhua Liu,Shaohua Tao,Kaihua Xu,Hongcai Chen,“A new complex networks evolving model”,Accepted by The Second International Conference on Complex Systems and ApplicationsModeling,Control and Simulations(ICIDSA07),Jinan,China,2007.7.3.Kaihua Xu,Jiwei Cao,Yuhua Liu,Shaohua Tao,“An Algorithm of Topol
21、ogy Discovery in Large Multi-Subnet Physical Network”,Proceedings of the International Multi-Symposiumson in Computer and Computional Science(IMSCCS|06).IEEE Computer Society Order Number P2581 ISBN 0-7695-2581-4,Hangzhou,Zhejiang,China,20-24 June 2006,pp.101-104.(EI/ISTP收录)。4 陶少华，刘玉华，许凯华，曹继伟，复杂网络的自相似性研究，中山大学学报（自然科学版），2006年第45卷 pp.68-71.（EI收录）。5 陶少华，刘玉华，许凯华，贾永灿，基于容量维数的复杂网络自相似性研究，计算机工程，2008年第2期。6 陶少华，刘玉华，许凯华，谈德茂，无尺度网络中避免集散节点形成的策略，计算机工程与应用，2007年43卷第2期，PP151-153.7 陶少华，刘玉华，许凯华，黄浩，基于信息维数的复杂网络自相似性研究，计算机工程与应用，2007年第15期。,谢谢各位老师及同学！,
