复杂网络演化模型研究.ppt

答 辩 人: 陶少华 指导老师: 刘玉华 教授复杂网络演化模型研究 及拓扑结构优化提纲1. 复杂网络概述 2.自相似性复杂网络模型的建立 3.自相似网络模型测量方法的深入讨论 4.基于吸引因子的网络模型的建立 5.无尺度网络拓扑结构优化的研究 6.结论与展望 7.参考文献 8.参加课题、发表文章1.复杂网络概述n 1960年，提出了随机网络（ER）模型 .n 1998年，提出了小世界网络模型n 1999年，提出了无尺度模型n 随后又提出了许多BA的扩展模型2.自相似性复杂网络 演化模型的建立n自相似性网络的形成是根据节点之间的信息传 递性，节点之间传递的信息有共同或相似性， 则建立连接 n如社会中人们之间的交往n节点传递信息，最终形成网络的自相似性质n社会网络中，如“物以类聚，人以群分”n模型生成算法可以描述为如下过程：n 节点 对自身有认知，向其周 围节点传递信息，如果节点彼此之间传递 的信息具有相同或相似性，则建立连接n网络中加入新节点 新节点与 老节点彼此向对方传递信息，有相似之处 则连接。

n如果节点 的m个属性与节 点 的m个属性有相似的信息 则表示为： 相似连接， 与节点 连接的概率依赖 于相似的程度，连接概率服从如下的规则 n信息传递模型表示节点对 在第i个属性下的 相似度（即相似的程度） n假设每个节点v有m个属性, 表示节点对 在第i个属性下的相似 程度n推导过程如下：模型的数学验证n由上述模型可知，在t时刻，网络的节点 数为N，则f(N)可表示为：n每隔一个时间段网络就增加新节点，即节点总 数增加一个单位，f在由时间h分隔的相互间的 自相关函数n则自相关函数满足: 仿真结果n本文分别以网络节点100、500、1000与 1500时形成的网络为例 3.自相似网络模型测量 方法的深入讨论n节点的分布具有不均匀性n为了能够客观的反映每个盒子中覆盖的 节点数，用信息维数进行测量n对容量维数进行如下改进 ：n对每个覆盖盒子按填充程度进行编号;n统计出分形结构落入第 i 只盒子的概率Pi(r)：n得出信息公式 n信息维数公式 仿真结果n以节点数100、500、1000为例：4.吸引因子存在的网络模型 问题的提出nBA模型预测全部的节点随着时间的增长 增加他们的连接数量。

n许多实例表明在真实系统中一个节点的 连接与增长率并不仅仅是依赖节点进入 网络的长短 基于吸引因子演化 网络模型的建立n网络增长，在每一个时间步里，具有吸引因子 的新节点被加进来n新节点与老节点相连的概率依赖于 与 ， 规则如下：n 模型参数的讨论 n当 大， 也大时，这时这种节点在与 新节点相连时就有很大的优势n当 大， 小时，这就相当于一个老节 点日趋衰落，没有太大的优势n当 小， 大时，这种情况下对新节点 很有利 仿真结果 n吸引因子模型与BA模型，度与度分布的 比较：5.无尺度网络模型 拓扑结构优化研究n具有很强的鲁棒性n同时也有脆弱性n改变无尺度网络集散节点的拓扑结构， 以增强网络的抗协同 攻击能力n 层次式处理与分布式处理层次式处理n建立节点度数统计表 ,在网络中当每一个节点的连接数 达到一个阈值,就认为该节点是集散节点. n此时如果还有新的要连接，则建立虚拟节点，其后新 进的节点粘贴到虚拟节点上 n依此类推，在逻辑上形成虚拟节点的层次结构 ，以层 二叉树为例 n如果一个节点出了故障，由父节点或子 节点或同一层相邻节点来代替它。

n每次要连接时，对层次结构从上到下进 行遍历，搜索度数小于R的虚拟节点，一 旦找到，则粘贴到这个节点上 模型的 控制算法如下：n增长性：假设网络最初有个 节点，当 加入一个新节点时，新节点通过 条新加入的边与网络中已有的 个节点 相连n优先粘贴 : 粘贴概率服从如下规则n约束控制 ：节点的最大度 若 ，则生成新的虚拟节点n节点遍历：如果有新涌现的节点与老节 点相连，则遍历与其下层的虚拟节点， 找到其中第一个度数值小于的节点与之 相连分布式处理n集散节点除控制为层次结构外，还可以控制为 分布式处理n超立方体结构是分布式系统中的一种结构 ,以 三维立方体为例，将网络拓扑结构生成为一个 三维立方体 .n过程如下：n生成7个虚拟节点，与原有的一个节点组 成三维立方体结构的8个顶点n每一节点均与相邻的三个节点相连结 n相互连结的节点，必须遵循如下原则： 两两相连的节点当且仅当和 的二进制编 码有一位不同n对节点的度数设定一个阈值，超过这个 值，新节点则连接到它相邻的节点上 n由于立方体结构节点之间信息互通n每个节点连接的数远小于集散节点的连 接数，因此当其中一个节点出现故障时 ，不影响整个系统的运行.n可扩展为n维立方体结构。

仿真结果 n原有集散节点结构n 层次式结构n立方体结构：n经过控制的集散节点形成层次结构或超 立方体结构的度分布较均匀，并且当某 个节点出了故障可以由其它节点迅速的 代理它 n与集散节点相比较层次结构与立方体结 构具有很强的稳健性与鲁棒性6.结论n创新点： 1.利用节点之间信息传递的方式，提出了自相似性的复杂 网络模型 2.分析了容量维数的不足，并用信息维数方法，对自相似 网络的测量进行了深入讨论 3.根据每个节点内在具有的吸引力，提出了基于吸引因子 的复杂网络模型 4.对无尺度网络模型的拓扑结构的优化进行了研究，提出 了采用层次式与分布式处理，增强了网络的稳健性展望n自相似性还有待深入讨论n吸引因子的变化规律还有待研究参考文献[1] 祁国宁，徐福缘，王怛山，复杂网络-系统结构研究文集，浙江大学现代制造工程研究所 [2] Erdòs P. and Rény A., On the evolution of random graphs, Publication of the Mathematical Institute of the Hungarian Academy of Science 5, 1960, pp.17~61. [3] Watts D.J.and Strogatz S.H., Collective dynamics of small-world networks, Nature 393,1998, pp.440~442. [4] Barabasi, A.-L. & Albertr, Emergence of scaling in random networks. Science , 1999. [5]Albert- Laszlo,Barabasi and Eric Bonaber, Scale-Free Networks, Scienti American 5.2003:pp.50~59. [6] Solomonoff R. and Rapoport A., Connectivity of random nets, Bulletin of Math. Biophys. 13, 1951, pp. 107~117. [7] Newmana M.E.J. and Watts D.J., Reormalization group analysis of the small-world network model, Phys. Lett. A 263, 1999, pp.341~346. [8] Albert R., Jeong H., and Barabási A.-L., Diameter of the world-wide web, Nature 401, 1999, pp.130~131. [9] Barabási A.-L., Albert R., and Jeong H., Mean-field theory for scale-free random networks, Pyhsica A 272, 1999, pp.173~187. [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 Barabási A.-L., Measuring preferential attachment in evolving networks, Europhys. Lett. 61, 2003, pp.567~572. [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.337~344. [13] Krapivsky P. L., Redner S., and Leyvraz F., Connectivity of growing random networks, Phys. Rev. Lett. 85, 2000, pp.5234~5237. [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 Barabási A.-L., Topology of evolving networks: local events and university, Phys. Rev. Lett. 85, 2000, pp.5234~5237.[16] Shi D.H., Liu L. M., Zhu 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 Fitness, 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] 王世俊，关于Weier。