复杂网络模型研究

《复杂网络模型研究》由会员分享，可在线阅读，更多相关《复杂网络模型研究（30页珍藏版）》请在金锄头文库上搜索。

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

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

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

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

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

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

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

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

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

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

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

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

13、络上覆盖边长r为的小正方形，统计有多少个 正方形中含有被测对象，为每一个正方形进行编号，统计 出节点落入盒子中的概率，记入p(r)中。l(2) 缩小正方形边长，再统计有多少个正方形中含有被测 对象，再统计出节点落入盒子中的概率，记入p(r)中。以此类推。l(3) 统计不同的值下记入的值。l(4) 根据不同的r值，计算不同的D值，最后得 出信息维数分别计算出处于不同阶段网络的自 相似信息维数D1、D2、D3。如果D1，D2、D3 取相同或相近值，则表明网络具有自相似性。进一步研究的方向l 许多复杂网络存在类似分数维的自相似性 指数, 从而也具有某种内在的自相似性。但大 多数实际网络不存在包含这些

14、网络的自然的欧 式空间, 而且复杂网络上两个节点之间的距离, 并不是指这两个节点之间的欧式距离, 而是指 连接这两个节点之间的最短路经包含的边数, 因此不能用盒计数法计算复杂网络中的自相似 分数维, 该问题的有效近似算法是非常值得研 究的。参考文献1 ERDOS, P. & R.ENYI, A. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 1960,5, 17-61 2 Barabasi, A.-L. & Albertr, Emergence of scaling in random network

15、s. 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. Nature, 1998, 393, 440-442 . 5Watts D.J.and Strogatz S.H., Collective dynamics of small-world networks, Nature 393,1998, pp.440442 6 Bianconi.G,Barabasi.A.L, Competition and multi-scaling in evolving networks, Europhys. Lett, 2001,54, 436-442谢谢