复杂网络的自相似性研究

1、2021/3/101 复杂网络的自相似性研究复杂网络的自相似性研究 报告人：陶少华 导 师：刘玉华教授 2006年1月 2021/3/102 v引言引言 v复杂网络模型简介复杂网络模型简介 v复杂网络的自相似性研究复杂网络的自相似性研究 v仿真分析仿真分析 v结论结论 v参考文献参考文献 2021/3/103 1.引言引言 v1960年数学家Erdos和Renyi提出了随机图理论，研 究复杂网络中随机的拓扑模型，自此ER模型一直是 研究复杂网络的基本模型。但是，但是近年的研究 发现：现实网络中得到的许多实验数据结果与随机 图模型并不符合，因此需要新的网络模型合理描述 实际网络。1998年Wat

2、ts和Strgatz提出了小世界 （WS）模型2，刻画了真实的网络所兼有的大聚 簇和短平均路径距离的特性。然而现实世界中的网 络还被统计到极少数接点拥有大量的连接，而众多 的接点仅具有少量连接的特性，这些也无法用随机 图模型加以合理解释。 2021/3/104 v1999年Barabasi和Albert提出了无尺度模型（BA） 3。BA模型指出了决定互联网、万维网等网络具有 无尺度模型的两个基本原理：增长性和择优连接。 虽然小世界网络与无尺度网络刻画了网络的基本特 性，但它们是基于对现实网络进行简化的前提下得 到的结果。因此我们有必要对复杂网络建模进行深 入研究，使它更加符合现实世界。本文提出

3、了网络 的自相似性，网络通过节点与节点相连汇聚形成， 节点与节点之间是通过某种共性而连接在一起的。 如人际关系之间的“物以类聚，人以群分”。 。 2021/3/105 2 .复杂网络模型简介复杂网络模型简介 v复杂网络就是具有复杂拓扑结构和动力行为 的大规模网络，它是由大量的节点通过边的 相互连结而构成的图。根据不同的拓扑结构 复杂网络可以分为规则网络，随机网络，小 世界网络，无尺度网络等等 。 2021/3/106 2.1 小世界网络模型小世界网络模型 v1998年，Watts 和Strogatz提出了小世界网 络模型。这个模型介于规则网络和随机网络 之间并在他们之间起桥梁作用。建立网络模

4、型步骤如下 ： v初始化：从具有个 节点的环形网络开始， 其中每一节点都与它初始的 个邻居相连 （在每一边有 个邻居）。 N 2k k 2021/3/107 v随机化：以概率 随机为规则网络的每条边 重新连线，同时保证没有自连结和重连边， 这一过程引进 条长距离捷径（重新连结的 边）边，它们连结那些拥有不同邻居的部分 节点。当 =0时，对就的为网络规则图，当 时 ，对应的为随机网络图，当 介于 （0,1）区间任意值时，模型显示出小世界特 性 。 p pNK p 1p p 2021/3/108 （1）规则图 （2）小世界 （3）随机图 2021/3/109 v小世界网络的主要特点： v度分布为指

5、数分布且峰值取平均值，每个节 点有大致相同数目的连结数，平均路径短且 聚集系数大如图，其中 为平均路径， 为聚集系数。小世界网络介于规则网络和随 机网络之间，它实现了从规则到完全随机之 间的连续演变。 L C 2021/3/1010 2.2 无尺度网络模型无尺度网络模型 v1999年，Barabasi和Albert提出了无尺度网 络模型，它通过增加新的节点而实现连续增 长，同时这些新的节点总是倾向于选择连结 已经具有大量连结的节点。BA模型具体描 述如下： v增长性：假设网络最初有 个节点。每一次 加入一个新节点，每次加入的新节点通过 条新加入的连结边与网络中已有的 0 m 0 ()mm 20

6、21/3/1011 v 个节点相连。 v优先连结：我们假设每个新节点与节点 相 连的概率 都依赖于节点 的度 ，并且 这个概率服从如下的规则： v v根据上述步骤重复 次后得到一个有 个节点和 条边的网络 。 m i i k i i k i i j j k k k t0 Ntm mt 2021/3/1012 2021/3/1013 v在1999年.Barabsi,与Albert用数量模拟表明 具有k条边的节点的概率服从指数为r=3的幂 律分布，如图3： 2021/3/1014 v无尺度网络的主要特点为度分布为幂律分布， 极少数节点有大量的连结，而大多数节点只 有很少的连结。同时，无尺度还具有某

7、些重 要特性，可以承受意外的故障，但对恶意攻 击却很脆弱。 2021/3/1015 3. 自相似性复杂网络自相似性复杂网络 v3.1问题的提出 v虽然小世界网络、无尺度网络比较准确地把握了现 实世界中网络最基本的特性，但它们仍然存在一定 的局限性。在现实世界中一些网络常常并不具有幂 律特征，如指数中止、小变量饱和等。为了在微观 层面更深入研究复杂网络的拓扑结构和演化规律， 研究人员作了大量新的尝试和努力，对网络的演化 与建模已经有了长足的进展，演化因素包括各种类 型的择优连接、局域世界、适应度4、竞争等。 2021/3/1016 v尽管众多的网络演化模型已经被用来分析和 研究可能潜藏的演化规律

8、，但这些研究仍然 忽视了一些重要因素。例如计算机网络节点 之间的连接。如果是按照择优连接概率：则 新的节点会全部连接到同一个节点上，但现 实网络并非如此，而是形成不同的集散节点。 这个例子说明了网络节点之间的连接有可能 是基于一些相似的性质，节点与节点之间有 某种共性才相连。因此建立并研究基于相似 性的网络演化模型有利于我们更好地认识现 实世界中的复杂网络 。 2021/3/1017 3.2 自相似性网络容量维数自相似性网络容量维数 v1975 年美国数学系教授曼德布罗特首次提出 了“分形”概念，其原意是“不规则的、非 整数的、支离破碎的”物体，我们把具有某 种自相似性的图形或集合称为分形。

9、大自然中存在的不规则的物体，可能存在不 同尺度上的相似性，称为自相似性。 2021/3/1018 v自相似性就是局部与整体相似，局部中又 有相似的局部，每一小局部中包含的细节 并不比整体所包含的少，不断重复的无穷 嵌套，形成了奇妙的分形图案，它不但包 括严格的几何相似性，而且包括通过大量 的统计而呈现出的自相似性。 v自然界存在大量统计意义下的自相似体， 一般并不知道自相似比。 2021/3/1019 v为了解决这类物体的维数计算，发展了计 算容量相似维数方法。常用的容量维数分 析方法有变方法、结构函数法，自仿射法 以及盒子覆盖算法。其中盒子覆盖算法简 单、快速、精确得到广泛应用。本文采用 盒

10、子覆盖算法来计算网络容量维数。计算 相似比时，采用圆片（或方块）去填充 （或覆盖）被测对象，统计覆盖所需的方 块数来计算其维数。如此方法计算的维数 称为容量维数。 2021/3/1020 v如果用长度为 尺子去测长度为 的线段，与 之比为 。 值的大小与 长短有关，越小 越大：。 对于 维物体： v v取对数得容量相似维数： rLL rN N rr N 1 Nr r c D 11 lim cc DD N rN r rr log lim 1 log c N r D r 2021/3/1021 v3.3 自相似特性测量方法自相似特性测量方法 v现实中的网络是动态增长的，为了测量复 杂网络的自相似性

11、，以网络的增长为例来 测量不同阶段网络的自相似维数。不同阶 段的网络为：起初形成的小局部网络，增 长稍大些的网络，再到最终形成的网络。 测量它们的自相似性维数的具体方法是： 2021/3/1022 v1 在被测网络上覆盖边长为 r 的小正方形， 统计一下有多少个正方形中含有被测对象， 记入 N(r)中。 v2 缩小正方形边长，再统计一下有多少个 正方形中含有被测对象，记入N(r)中，以此 类推。 v3 统计不同的值下记入的值。 2021/3/1023 v分别计算出处于不同阶段网络的自相似容量 维数 、 、 与 。如果这几个维数取相同 或相近值（容量维数具有最小标度与最大标 度），则表明网络具有

12、自相似性。 1c D 2c D 3c D 4c D 2021/3/1024 3.3 仿真结果与分析仿真结果与分析 v本文分别以网络节点n=100、n=500、n=1000与 n=1500时形成的网络为例。N=100时形成的网络作 为小局部网络，网络增加节点至n=500以及继续增 加节点至n=1000时形成的这两类网络为大的局部网 络。此后网络继续增长，最终形成的网络节点 n=1500。用盒子覆盖方法测量这四类网络在不同值 下的，并由实验数据绘出仿真图形（如图4）。 v 2021/3/1025 2021/3/1026 v 根据实验得出的数据用最小二乘法对 v进行线性拟合，得出直线方程的斜率即为

13、相似维数Dc,网络节点n=100时Dc1=1.56, n=500时，Dc2=2.98, n=1000时， Dc3=2.85,n=1500时，Dc4=2.41,Dc2、 Dc3与Dc4的值取相近的一系列值，表明在 现实中不断增长的复杂网络的确具有自相 似性。 log lim 1 log c Nr D r 2021/3/1027 v网络起初形成时 n=100,而Dc1=1.56， Dc2=2.98,Dc3=2.85与Dc4=2.41有一定的 偏差，这也在一定程度上说明了随着网络 的增长具有的自相似性越来越明显。图4中 的图形均呈幂律分布这也与复杂网络中无 尺度特性的度分布为幂律分布相吻合。 202

14、1/3/1028 4 结论结论 v本文在详细阐述复杂网络的小世界模型与无 尺度模型的演化过程之后，提出了复杂网络 的自相似性质，引进了分形数学思想，给出 了具体的计算相似容量维数方法，并用此方 法分析了复杂网络在不同阶段的容量维数， 得出维数相同（或相近）具有自相似的特性， 又给出了仿真分析结果。 2021/3/1029 v为了更深入地了解各种复杂网络（从 生物基因进化网络到像语言学、世界 贸易网、社会经济网络等等）中的微 观演化过程， 用盒子覆盖方法测量复杂网络的自相 似性是一种强有力的工具，本文所提 出的复杂网络的自相似性还有待更进 一步的研究。 2021/3/1030 vAlbert R

15、. & Barabasi, A.-L. Statistical mechanics of complex networks. Rev. Mod. Phys 74,47-97（2002） vPastor-Satorras, R. & Vespignani, A. Evolution and Structure of the Internet: a Statistical Physics Approach (Cambridge University Press, Cambridge, 2004). 参考文献 2021/3/1031 vNewman, M. E. J. The structure and function of complex networks. SIAM Review 45, 167-256（2003）. vChaoming Song, Shlomo Havlin, Hernan A. Makse1.letters to nature,2005. vR. Guimera, L. Danon, A.