几种复杂网络模型21 随机网络模型

1、复杂网络模型研究复杂网络模型研究主讲人：孟永伟目录目录l引言l几种复杂网络模型l复杂网络模型研究现状l进一步研究的方向l参考文献1.引言引言l 近年来，复杂网络引起了许多相关领域研究人员的关注。所谓复杂网络就是具有复杂拓扑结构和动力行为的大规模网络，它是由大量的节点通过边的相互连接而构成的图。复杂网络的节点可以是任意具有特定动力和信息内涵的系统的基本单位，而边则表示这些基本单位之间的关系或联系。例如，Internet网，WWW网络，社会关系网络，无线通讯网络，食物链网络，科学家合作网络，流行病传播网络等都是复杂网络。我们生活中存在着大量的复杂网络，这促使我们去研究这些复杂网络的行为。l 然而,

2、 迄今为止, 复杂网络还没有一个精确的定义。从目前的研究来看, 它主要包含两层含义: 一、它是大量真实系统的拓扑抽象; 二、它介于规则网络和随机网络之间, 比较难于实现, 目前还没有生成能够完全符合统计特征的复杂网络。网络化是今后若干年许多研究领域发展的一个主流方向，因此对复杂网络的研究具有重大的科学意义和应用价值2 几种复杂网络模型几种复杂网络模型2.1 随机网络模型随机网络模型l描述一个网络最早要追溯到1736年，欧拉致力于著名的“哥尼斯堡七桥问题”的研究，图形理论由此萌芽，欧拉也因此被称为“图论”之父。1960年匈牙利数学家Erdo.s and Rnyi 建立了随机图理论, 研究复杂网络

3、中随机拓扑模型（ER），自此ER模型一直是研究复杂网络的基本模型1。随机网络的两种描述方式如下：l随机网络ER模型的第一种描述方式2：给定网络节点总数N，网络中任意两个节点以概率P连接，生成的网络全体记为G(N,P)，构成一个概率空间。由于网络中连线数目是一个随机变量X，取值可以从0到 ，有n条连线的网络数目为 。因此，可生成的不同网络的总数为 ，它们服从二项分布。12NN 2)1(NNnC122N Nl随机网络ER模型的第二种描述方式3：给定网络节点数N连线总数n，而这些连线是从总共 条可能的连线中随机选取的，生成的网络全体记为G(N,P)，构成一个概率空间。这样，可生成的不同网络的总数为

4、，它们出现的概率相同，服从均匀分布。12N N 2)1(NNnC2.2 小世界网络模型l 自从提出随机图理论以后，ER模型一直是研究复杂网络的基本模型。但是近年的研究发现：现实中得到的许多试验数据结果与随机图模型并不符合，1967 年美国社会心理学家Milgram 通过“小世界试验”, 提出了“六度分离推断”, 即地球上任意两人之间的平均距离为6, 也就是说只要中间平均通过5 个人, 你就能联系到地球上的其他任何人。随后,一些数学家也对此进行了严格的证明。1998年Watts 和Strogtz提出了“小世界”网络模型(WS ) 4，刻画了真实网络所有的大聚簇和短平均路径距离的特性。小世界网络的

5、基本模型是WS模型，算法描述如下5：l(1) 给定规则网：假如我们有一个节点总数为 N,每个节点与它最近邻的节点K=2k相连线的 一维有限规则网，通常求 ；l(2) 改写旧连线：以概率p为规则网的每条旧连线重新布线，方法是将该连线的一个端点随机地放到一个新位置上，但需要排除自身到自身的连线和重复连线。1N K l 因为不允许重复连线，给定的规则网只有条连线 。重新布线时，依次对每条旧连线选定的某一边的端点随机放置新位置，因此改写的连线数目为 。由于随机性的缘故，这些改写的连线可能会出现远距离的连线，它们被称为捷径。显然，当p=0时，仍为给定的规则网，当p=1时，我们将得到一个特殊的随机网。随着

6、p的增加，人们可以看到从规则网到随机网的变化。如图2.3。2pNK2NK 图2.3 规则网、小世界网、随机网2.3 无尺度网络模型无尺度网络模型l WS模型能够反映现实网络的小世界特征，然而现实世界中的网络还被统计到极少节点拥有大量的连接，而众多的节点仅具有少量连接的特征，这些也无法用随机模型加以合理解释。1999年Barabasi和Albert提出了无尺度模型（BA）6。在该模型中提出了两个重要的网络演化机理：增长和择优。lBA模型的算法描述如下：l初始：开始给定n0个节点；l增长：在每个时间步重复增加一个新节点和 m(m=n0)条新连线；l择优：新节点按照择优概率 选择旧节点i与之连线，其

7、中ki是旧节点i的度数 iijjkkkl在1999年.Barabsi,与Albert用数量模拟表明具有k条边的节点的概率服从指数为r=3的幂律分布，如下图所示：3 复杂网络模型研究现状复杂网络模型研究现状l3.1基于信息传递的自组织模型l目前为止, 针对计算网络拓扑主要是基于Barabsi 和Albert 提出来的复杂网络演化模型(BA 模型) 和其改进型的局部演化模型, 在路由器和自治域这两种不同的层次来描述计算机网络的拓扑结构。l 优先连接对于描述新节点的加入过程比较粗糙，因为首先：新节点在加入网络之前，很难得到已有网络的全局信息；其次，单一的优先连接不能够描述复杂的加入决策过程，而且在全

8、网中容易形成少量的集散节点。因此，要建立更加符合现实Internet拓扑特征的网络模型则需要考虑更完善的加入规则， 基于此问题提出了信息传递的自组织模型。自组织层次网络的构建步骤如下：l1) 在一个矩形中随机均匀分布一些点代表网络节点;l2) 初始化，给每个节点分配一个定时器(到达某个时间后，节点才开始活动);l3) 节点开始活动，节点的活动分为发送消息和接收消息。每条消息含有节点ID及节点的度等信息。节点的度等参数决定了该节点发出的消息的辐射范围，还决定了该节点能够收到来自多大范围内的消息;l4) 每个节点将一定时期内收到的消息用相应的规则计算后选择其中一个消息源与之建立连接。经过一段时间的

9、进化后，一个具有层次结构的复杂网络就涌现出来。l(A) (B) (C)l自组织层次网络的形成过程l3.2 基于容量维数模型l 虽然小世界网络、无尺度网络比较准确地把握了现实世界中网络最基本的特性，但它们仍然存在一定的局限性。为了在微观层面更深入研究复杂网络的拓扑结构和演化规律，研究人员作了大量新的尝试和努力，对网络的演化与建模已经有了长足的进展，演化因素包括各种类型的择优连接、局域世界、适应度、竞争等。尽管众多的网络演化模型已经被用来分析和研究可能潜藏的演化规律，但这些研究仍然忽视了一些重要因素。例如计算机网络节点之间的连接。如果是按照择优连接概率： ，则新的节点会全部连 iijjkkkl接到

10、同一个节点上，但现实网络并非如此，而是形成不同的集散节点。这个例子说明了网络节点之间的连接有可能是基于一些相似的性质，节点与节点之间有某种共性才相连。因此建立并研究基于相似性的网络演化模型有利于我们更好地认识现实世界中的复杂网络。l 1975 年美国数学系教授曼德布罗特首次提出了“分形”概念，其原意是“不规则的、非整数的、支离破碎的”物体，我们把具有某种自相似性的图形或集合称为分形。l 大自然中存在的不规则的物体，可能存在不同尺度上的相似性，称为自相似性。自然界存在大量统计意义下的自相似体，一般并不知道自相似比。为了解决这类物体的维数计算，发展了计算相似维数方法。计算相似比时，采用圆片（或方块

11、）去填充（或覆盖）被测对象，统计覆盖所需的方块数来计算其维数。如此方法计算的维数称为容量维数. l定义1 设F是的非空有界子集,Nr(F)是覆盖的长度至多为r的集合的个数.上、下盒计数维数分别定义为：l l l若它们是相等的，称其公共值为的盒计数维或盒子维数l _0lndimlimlnrBrN FFr _0dimlnlnlimrBrFNFr 0lndimlimlnrBrNFFr 这种叙述在实际中得到广泛应用，为了得到平面集合的盒维数我们可以画边长为的正方形或盒网，对各个充分小的计数覆盖的个数，维数是当时递增的对数比率，可用与图象的斜率来估计它的值。为简便起见，我们用下面公式来代替： l1 在被

12、测网络上覆盖边长为 r 的小正方形，统计一下有多少个正方形中含有被测对象，记入 N(r)中。l2 缩小正方形边长，再统计一下有多少个正方形中含有被测对象，记入N(r)中，以此类推。l3 统计不同的值下记入的值。loglim1logrcNFDrl分别计算出处于不同阶段网络的自相似容量维数Dc1,Dc2,Dc3与Dc4。如果这几个维数取相同或相近值（容量维数具有最小标度与最大标度），则表明网络具有自相似性。l3.3 基于信息维数网络模型l网络中节点的分布具有不均匀性 ，为了能够客观的反映每个盒子中覆盖的节点数，用信息维数进行测量。对容量维数进行如下改进 ：l对每个覆盖盒子按填充程度进行编号;l统计

13、出分形结构落入第 i 只盒子的概率Pi(r)：l得出信息公式 1logN rii riI rp rp iiN rp rN rl信息维数公式l测量它们的自相似性维数的具体方法是：l(1) 在被测网络上覆盖边长r为的小正方形，统计有多少个正方形中含有被测对象，为每一个正方形进行编号，统计出节点落入盒子中的概率，记入p(r)中。l(2) 缩小正方形边长，再统计有多少个正方形中含有被测对象，再统计出节点落入盒子中的概率，记入p(r)中。以此类推。0li m1lo girIrDr l(3) 统计不同的值下记入的值。l(4) 根据不同的r值，计算不同的D值，最后得出信息维数分别计算出处于不同阶段网络的自相

14、似信息维数D1、D2、D3。如果D1，D2、D3取相同或相近值，则表明网络具有自相似性。进一步研究的方向进一步研究的方向l 许多复杂网络存在类似分数维的自相似性指数, 从而也具有某种内在的自相似性。但大多数实际网络不存在包含这些网络的自然的欧式空间, 而且复杂网络上两个节点之间的距离, 并不是指这两个节点之间的欧式距离, 而是指连接这两个节点之间的最短路经包含的边数, 因此不能用盒计数法计算复杂网络中的自相似分数维, 该问题的有效近似算法是非常值得研究的。参考文献参考文献1 ERDOS, P. & R.ENYI, A. On the evolution of random graphs

15、. Publ. Math. Inst. Hung. Acad. Sci. 1960,5, 17-612 Barabasi, A.-L. & Albertr, Emergence of scaling in random networks. Science ,1999.3Erds 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.4 WATTS, D. J. & STROGATZ, S. H. Collective dynamics of small-world networks. Nat