复杂网络演化模型与其节点重要性分析

《复杂网络演化模型与其节点重要性分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕，{：学位论文1．3复杂网络演化模型研究概况本文的研究重点主要集中在网络生成机制及演化模型上，即通过生成机制建立模型，模仿真实网络行为，再现现实系统的主要拓扑特性。学术界十分关心网络结构的复杂性研究，主要原因之一是在很大程度上网络的结构决定了它的功能。近年来，复杂网络中的网络演化机制以及演化模型的研究最为活跃，目前，在这方面的研究已经取得了很多成果，在正式引入本文的工作之前，先对已有复杂网络模型方面的相关工作进行简要的介绍与评述。1．3．1规则网络人们把一维链，二维J下方晶格等称为规则网络。规则网络是指平移对称性晶格，任何一个格点的邻近数目都相同。常见的规则网络有

2、：(1)全局耦合网络：任意两个点之间都有边直接相连。这种网络在所有具有相同节点的网络中，平均路径长度最小(￡=1)和聚类系数最大(C=1)。(2)最近邻耦合网络：N个节点排成环状，其中每个节点都与它左右各K／2个邻居点相连，其中K是一个偶数。(3)星形耦合网络。它有一个中心点，其余N．1个点都只与这个中心点连接，而它们彼此之间不连接。1．3．2随机网络随机网络是指定每对节点以统一概率连接而成的。这种网络典型的模型是Erd6s和R6nyi于40多年前开始研究的ER随机图模型⋯】。在该模型中，节点数目N固定不变，并且假定任意节点之间有一条边连接的概率为尸，因此，这个网络

3、的边数是一个随机变量，其期望值为尸=Ⅳ(Ⅳ一1)／2。这种网络是从纯数学的角度研究的。图1．1给出了随机网络的演化过程。人们发现了随机图许多重要性质都是突然涌现的，而且Erd6s．R6nyi随机网络一些重要属性跟大部分现实世界有很大的不同。首先，随机网络没有展现高节点集聚特性，在现实世界中你可能是你朋友的朋友而不是一个随机的人。其次，随机网络的度分布邻近于高斯分布(当n取极限时，呈现泊松分布)，不同于现实世界观察到的幂律分布。OoO。Op=Op20．1p20．15p=O．25图1．1随机图的演化示意图复杂网络演化模型及】￡节点莺要件研究1．3．3小世界网络1998年

4、Watts和Strogatz在Nature杂志上发表文章，引入了小世界(Small-w6rld)网络模型【14J，文章中详细描述从完全规则网络转变成完全随机网络的演化过程。小世界现象【”】在社会学上也被称为“六度分离’’，1967年美国哈佛大学的社会心理学家MiIgram的一个实验【16】，这个实验给出的推断是：地球上任意两个人之间的平均距离是6。小世界网络既具有与规则网络类似的聚类特性，又具有与随机网络类似较小的平均路径长度。小世界模型构造算法如下：(1)从规则图开始：考虑一个含有N个点的最近邻耦合网络114】，它们围成一个环，其中每个节点都与它左右相邻的各K／2

5、节点相连，K是偶数。(2)随机化重连：以概率p随机地重新连接网络中的每条边，即边的一个顶点固定不变，在网络中随机取一个节点作为边的另一个顶点，其中任意两个不同节点之间有且只有一条边，并且不能有边连向自身节点。1．3．4无标度网络模型歙随机图和孵小世界模型的～个共同特征就是网络的连接度分布可近似用泊松分布来表示，该分布【14】的度平均值(七)处有一顶点值(峰值)，然后随着度值的增大曲线呈指数方式快速衰减。这意味着当七一(砖时，度为七的节点几乎不存在。因此，这类网络也称为均匀网络或指数网络。近年在复杂网络的另一重要发现就是许多复杂网络，包括Internet，WWW以及新

6、称代谢网络等的连接度分布函数具有幂律形式也就是p(七)～彳七一，指数，，的范围在(2，3)之间。它由于缺乏一个描述问题的特征尺度而被称为无标尺网络。为了解释幂律分布的产生机理，1999年Barabasi和Albert在Science上发表文章提出了一个无标度网络模型【3】，现称为BA模型。他们认为形成无标尺网络必须具备两个必要条件【3】：增长特性和优先(preferentialattachment)连接特性。由于新加入的节点更倾向连接具有较大连接度的节点，这样会导致“富人越富的”马太效应。例如：新发表的文章更倾向于引用一些已被广泛引用的重要文献，在度分布图上表现为拖

7、着一条长长的尾巴，即大部分节点只有少数几个连结，而某些节点却拥有与其他节点的大量连结。这些具有大量连接的点称为“Hub"节点。BA模型的节点度分布服从度指数等于3的幂律形式。大量实证结构表明，许多现实世界的复杂网络是无标度的。表1．1中列出了几种典型的网络【l71，研究并统计了这些网络的一些基本属性，其中包括实际网络的名称(Network)，网络大小(Size)，平均度值(<忌>)，Out度幂律分布指数(‰，)，In度幂律分布指数()，胁)，平均距离(f砌)，按随机图论为前提计算的平均距离(乙)，按Newman，strogata和watts构造的网络为前提计算的