复杂网络的自相似性研究.ppt

复杂网络的自相似性研究 报告人 陶少华导师 刘玉华教授2006年1月 引言复杂网络模型简介复杂网络的自相似性研究仿真分析结论参考文献 1 引言 1960年数学家Erdos和Renyi提出了随机图理论 研究复杂网络中随机的拓扑模型 自此ER模型一直是研究复杂网络的基本模型 但是 但是近年的研究发现 现实网络中得到的许多实验数据结果与随机图模型并不符合 因此需要新的网络模型合理描述实际网络 1998年Watts和Strgatz提出了小世界 WS 模型 2 刻画了真实的网络所兼有的大聚簇和短平均路径距离的特性 然而现实世界中的网络还被统计到极少数接点拥有大量的连接 而众多的接点仅具有少量连接的特性 这些也无法用随机图模型加以合理解释 1999年Barabasi和Albert提出了无尺度模型 BA 3 BA模型指出了决定互联网 万维网等网络具有无尺度模型的两个基本原理 增长性和择优连接 虽然小世界网络与无尺度网络刻画了网络的基本特性 但它们是基于对现实网络进行简化的前提下得到的结果 因此我们有必要对复杂网络建模进行深入研究 使它更加符合现实世界 本文提出了网络的自相似性 网络通过节点与节点相连汇聚形成 节点与节点之间是通过某种共性而连接在一起的 如人际关系之间的 物以类聚 人以群分 2 复杂网络模型简介 复杂网络就是具有复杂拓扑结构和动力行为的大规模网络 它是由大量的节点通过边的相互连结而构成的图 根据不同的拓扑结构复杂网络可以分为规则网络 随机网络 小世界网络 无尺度网络等等 2 1小世界网络模型 1998年 Watts和Strogatz提出了小世界网络模型 这个模型介于规则网络和随机网络之间并在他们之间起桥梁作用 建立网络模型步骤如下 初始化 从具有个节点的环形网络开始 其中每一节点都与它初始的个邻居相连 在每一边有个邻居 随机化 以概率随机为规则网络的每条边重新连线 同时保证没有自连结和重连边 这一过程引进条长距离捷径 重新连结的边 边 它们连结那些拥有不同邻居的部分节点 当 0时 对就的为网络规则图 当时 对应的为随机网络图 当介于 0 1 区间任意值时 模型显示出小世界特性 1 规则图 2 小世界 3 随机图 小世界网络的主要特点 度分布为指数分布且峰值取平均值 每个节点有大致相同数目的连结数 平均路径短且聚集系数大如图 其中为平均路径 为聚集系数 小世界网络介于规则网络和随机网络之间 它实现了从规则到完全随机之间的连续演变 2 2无尺度网络模型 1999年 Barabasi和Albert提出了无尺度网络模型 它通过增加新的节点而实现连续增长 同时这些新的节点总是倾向于选择连结已经具有大量连结的节点 BA模型具体描述如下 增长性 假设网络最初有个节点 每一次加入一个新节点 每次加入的新节点通过条新加入的连结边与网络中已有的 个节点相连 优先连结 我们假设每个新节点与节点相连的概率都依赖于节点的度 并且这个概率服从如下的规则 根据上述步骤重复次后得到一个有个节点和条边的网络 在1999年 Barab si 与Albert用数量模拟表明具有k条边的节点的概率服从指数为r 3的幂律分布 如图3 无尺度网络的主要特点为度分布为幂律分布 极少数节点有大量的连结 而大多数节点只有很少的连结 同时 无尺度还具有某些重要特性 可以承受意外的故障 但对恶意攻击却很脆弱 3 自相似性复杂网络 3 1问题的提出虽然小世界网络 无尺度网络比较准确地把握了现实世界中网络最基本的特性 但它们仍然存在一定的局限性 在现实世界中一些网络常常并不具有幂律特征 如指数中止 小变量饱和等 为了在微观层面更深入研究复杂网络的拓扑结构和演化规律 研究人员作了大量新的尝试和努力 对网络的演化与建模已经有了长足的进展 演化因素包括各种类型的择优连接 局域世界 适应度 4 竞争等 尽管众多的网络演化模型已经被用来分析和研究可能潜藏的演化规律 但这些研究仍然忽视了一些重要因素 例如计算机网络节点之间的连接 如果是按照择优连接概率 则新的节点会全部连接到同一个节点上 但现实网络并非如此 而是形成不同的集散节点 这个例子说明了网络节点之间的连接有可能是基于一些相似的性质 节点与节点之间有某种共性才相连 因此建立并研究基于相似性的网络演化模型有利于我们更好地认识现实世界中的复杂网络 3 2自相似性网络容量维数 1975年美国数学系教授曼德布罗特首次提出了 分形 概念 其原意是 不规则的 非整数的 支离破碎的 物体 我们把具有某种自相似性的图形或集合称为分形 大自然中存在的不规则的物体 可能存在不同尺度上的相似性 称为自相似性 自相似性就是局部与整体相似 局部中又有相似的局部 每一小局部中包含的细节并不比整体所包含的少 不断重复的无穷嵌套 形成了奇妙的分形图案 它不但包括严格的几何相似性 而且包括通过大量的统计而呈现出的自相似性 自然界存在大量统计意义下的自相似体 一般并不知道自相似比 为了解决这类物体的维数计算 发展了计算容量相似维数方法 常用的容量维数分析方法有变方法 结构函数法 自仿射法以及盒子覆盖算法 其中盒子覆盖算法简单 快速 精确得到广泛应用 本文采用盒子覆盖算法来计算网络容量维数 计算相似比时 采用圆片 或方块 去填充 或覆盖 被测对象 统计覆盖所需的方块数来计算其维数 如此方法计算的维数称为容量维数 如果用长度为尺子去测长度为的线段 与之比为 值的大小与长短有关 越小越大 对于维物体 取对数得容量相似维数 3 3自相似特性测量方法现实中的网络是动态增长的 为了测量复杂网络的自相似性 以网络的增长为例来测量不同阶段网络的自相似维数 不同阶段的网络为 起初形成的小局部网络 增长稍大些的网络 再到最终形成的网络 测量它们的自相似性维数的具体方法是 1在被测网络上覆盖边长为r的小正方形 统计一下有多少个正方形中含有被测对象 记入N r 中 2缩小正方形边长 再统计一下有多少个正方形中含有被测对象 记入N r 中 以此类推 3统计不同的值下记入的值 分别计算出处于不同阶段网络的自相似容量维数 与 如果这几个维数取相同或相近值 容量维数具有最小标度与最大标度 则表明网络具有自相似性 3 3仿真结果与分析 本文分别以网络节点n 100 n 500 n 1000与n 1500时形成的网络为例 N 100时形成的网络作为小局部网络 网络增加节点至n 500以及继续增加节点至n 1000时形成的这两类网络为大的局部网络 此后网络继续增长 最终形成的网络节点n 1500 用盒子覆盖方法测量这四类网络在不同值下的 并由实验数据绘出仿真图形 如图4 根据实验得出的数据用最小二乘法对进行线性拟合 得出直线方程的斜率即为相似维数Dc 网络节点n 100时Dc1 1 56 n 500时 Dc2 2 98 n 1000时 Dc3 2 85 n 1500时 Dc4 2 41 Dc2 Dc3与Dc4的值取相近的一系列值 表明在现实中不断增长的复杂网络的确具有自相似性 网络起初形成时n 100 而Dc1 1 56 Dc2 2 98 Dc3 2 85与Dc4 2 41有一定的偏差 这也在一定程度上说明了随着网络的增长具有的自相似性越来越明显 图4中的图形均呈幂律分布这也与复杂网络中无尺度特性的度分布为幂律分布相吻合 4结论 本文在详细阐述复杂网络的小世界模型与无尺度模型的演化过程之后 提出了复杂网络的自相似性质 引进了分形数学思想 给出了具体的计算相似容量维数方法 并用此方法分析了复杂网络在不同阶段的容量维数 得出维数相同 或相近 具有自相似的特性 又给出了仿真分析结果 为了更深入地了解各种复杂网络 从生物基因进化网络到像语言学 世界贸易网 社会经济网络等等 中的微观演化过程 用盒子覆盖方法测量复杂网络的自相似性是一种强有力的工具 本文所提出的复杂网络的自相似性还有待更进一步的研究 AlbertR Barabasi A L Statisticalmechanicsofcomplexnetworks Rev Mod Phys74 47 97 2002 Pastor Satorras R Vespignani A EvolutionandStructureoftheInternet aStatisticalPhysicsApproach CambridgeUniversityPress Cambridge 2004 参考文献 Newman M E J Thestructureandfunctionofcomplexnetworks SIAMReview45 167 256 2003 ChaomingSong ShlomoHavlin Herna nA Makse1 letterstonature 2005 R Guimera L Danon A D az Guilera Self similarcommunitystructureinanetworkofhumaninteractions PHYSICALREVIEWE68 065103 R 2003 谢谢