第二章 复杂网络模型

1、第二章 复杂网络模型 规则网络 随机图 小世界网络 无标度网络 规则网络 系统中节点及其与边的关系是固定的。 （a）全局耦合网络； （b）最近邻耦合网络； （c）星形网络 具有最小的平均路径长度Lgc =1和最大的聚类 系数Cgc =1； 最近邻耦合网络最近邻耦合网络:含N个围成一个环的点，其中每个节点都 与它左右各K/2个邻居点相连（K为偶数），对于较大的K 值，最近邻耦合网络的聚类系数为 因此，这样的网络是高度聚类的。对于固定的K值，网络平 均路径长度为 星形耦合网络：有一个中心点，其余N-1个点都只与这个中 心点连接，其平均路径长度为 聚类系数为 4 3 )1(4 )2(3 K K C

2、nc )(N )(N2 ) 1( ) 1(2 2 NN N Lstar 1 1 N N Cstar )(N K N Lnc 2 随机图 随机图是与规则网络相反的网络，一个典型模型是Erdos 和Renyi于40多年前开始研究的随机图模型。 假设有大量的纽扣（N1）散落在地上，并以相同的概率 p给每对纽扣系上一根线。这样就会得到一个有N个节点， 约pN(N-1)/2条边的ER随机图的实例。 ER随机图的性质 随机图理论的一个主要研究课题是： 当概率p为多大时，随机图会产生一些特殊的属性？ Erdos和Renyi系统地研究了当 时，ER随机图的性质与概 率p之间的关系，他们采用了如下定义： 如果当

3、 时产生一个具有性质Q的ER随机图的概率为1，那 么就称几乎每一个ER随机图都具有性质Q。 Erdos和Renyi的最重要的发现时ER随机图具有如下的涌现或相 变性质： ER随机图的许多重要的性质都是突然涌现的。也就是说，对 于任意给定的概率p，要么几乎每一个图都具有性质Q，要 么几乎每一个图都不具有该性质。 上述纽扣网络，如果p大于某个临界值 ，那么几乎 每一个随机图都是连通的。 N N NNpc/ )(ln ER 随机图的平均度是 ,平均路径长度 。LER为网络规模的对数增长函数是典 型的小世界特征。ER随机图的聚类系数是C=p=/N1， 这意味着大规模的稀疏ER随机图没有聚类特性。实际网

4、 络的聚类系数要比相同规模的ER随机图的聚类系数要高 得多。 ER随机图的度分布可用Poission分布来表示： 因此，ER随机图也称为“Poission随机图”。 kN LER ln/ln pN1)-p(Nk ! )1 ()( k pp k N kP ek kk kNk 六度分离理论 惊叹于世界是如此的渺小，总是发现你和 刚认识的另外一个人有共同的朋友不 禁问：世界到底有多大？我们和世界上其 他人距离有多远？答案是 6 ？ 六度分离理论 源于社会学 1967年，哈佛大学心理学教授Stanley Milgram做的送信实验： 六度分离理论 为什么蠕虫病毒在互联网上传播得那么快，二十四小时能 感

5、染几千万台主机？为什么SARS病毒很难遏制住传播， 总是逃开人们的封锁扩散开？ 在数学家的眼里，这一类问题都从它的实际意义中抽象了出 来，形成了一个叫小世界模型的东西，它是图论的一个新兴 分支学科复杂网络理论中的一个课题。 当图很大时，如何研究？ 通过统计的方法来研究这个图的性质。这就是复杂网络 理论。 六度分离理论 数学家的六度分离。 匈牙利伟大的数学家Paul Erds 与其他数学家的合作关系 在数学家的眼里，这一类问题都从它的实际意义中抽象了出 来，形成了一个叫小世界模型的东西，它是图论的一个新兴 分支学科复杂网络理论中的一个课题。 哥伦比亚大学的Duncan J. Watts 教授建立

6、了一个电影 数据库，分析每一个演员和Kevin Bacon之间的关系， 得到的平均值是2.918 六度分离理论 哥伦比亚大学一些对这个感兴趣的学者们，发起了一个 “小世界研究计划” 电子邮件 Duncan J. Watts的科普作品Six Degrees: The Science of a Connected Age ，该书现在已经有中译本六度：互联时代 的科学。 Duncan J. Watts的另一部半科普性质的作品Small Worlds : The Dynamics of Networks between Order and Randomness 小世界 小世界网络模型 哥伦比亚大学一些

7、对这个感兴趣的学者们，发起了一个 “小世界研究计划” 电子邮件 Duncan J. Watts的科普作品Six Degrees: The Science of a Connected Age ，该书现在已经有中译本六度：互联时代 的科学。 Duncan J. Watts的另一部半科普性质的作品Small Worlds : The Dynamics of Networks between Order and Randomness 小世界 小世界网络模型 作为从完全规则网络向完全随机图的过渡，作为从完全规则网络向完全随机图的过渡，WattsWatts 和和StrogtzStrogtz于于19981

8、998年引入了一个小世界网络模型，年引入了一个小世界网络模型， 称为称为WSWS小世界模型小世界模型。其构造算法如下：。其构造算法如下： P=0对应于完全规则网络，p=1对应于完全随机网络。 WS小世界模型的构造方法如下： (1)从规则图开始，考虑一个含有N个节点的规则网络，它 们圈成一个环，其中每个节点都与它左右相邻的各K2个 节点相连接，K为偶数； (2)随机化重连，以概率p随机地重新连接网络中的每条边 (将边的一个端点保持不变，而另一个端点取为网络中随 机选择的一个节点)，其中规定，任意两个不同的节点之 间至多只能有一条边，并且每一个节点都不能有边与其自 身相连。 下面3个图表示了小世界

9、网络的构造以及它与规则网络、 随机网络的关系。在WS小世界模型中，p0对应于规则 网络，pl则对应于完全随机网络，通过调节p的值就可 以控制从规则网络到完全随机图的过渡。因此小世界网络 是介于规则网络和随机网络之间的一种网络。 P = 0 = 0.1 =1 P=0K=6N=200 六度分离 P=0.1 K=6 N=200 六度分离 P=1K=3N=200 六度分离 小世界网络模型 小世界网络模型 Newman和Watts提出了NW小世界模型，用“随机化加 边”取代WS小世界模型构造中的“随机化重连”。 算法如下： 从规则图开始：含有N 个节点的最近邻耦合网 络。 随机化加边：以概率P在随机选取

10、的一对节点之 间加上一条边。 NW小世界模型中，p=0对应于原来的最近邻耦合 网络，p=1对应于全局耦合网络。 小世界网络模型 小世界网络的统计性质 1.聚类系数 WS小世界网络的聚类系数为 NW小世界网络的聚类系数为 2.平均路径长度 3 )1 ( ) 1(4 )2(3 )(p K K pC )2(4) 1(4 )2( 3 )( pKpK K pC )2/( 2 )(NKpf K N pL 其中f（u）为一普适标度函数，满足 Newman等人基于平均场方法给出了如下近似表达式： 3.度分布 在基于“随机化加边”机制的NW小世界模型中，每个节 点的度至少为K，因此当 时，一个随机选取的 节点的

11、度为k的概率为： 而当kK时，P（k）=0。 1uu/uln 1,tan )( ，）（ utcons uf 2 arctan 22 1 )( 2 x x h xx xf Kk KkNKk N Kp N Kp Kk N kP 1)( 无标度网络模型 小世界网络，随机网络的特征？ 无标度网络模型 小世界网络，随机网络没有考虑到的网络特征： 什么是无标度网络什么是无标度网络? 无标度网络是由Barabasi所命名的（BA模型)，该种网络具 有2种特性：不断增长和偏好连接。 不断增长： 早期的网络模型没有考虑结点数随着时间而增长。整个图形 是静止的。然而，在现实生活中，总有新人加入到社交网中， 总有新

12、的网站在internet上出现。于是乎，网络处在一个不断 增长的状态。 Hello! Nice to meet you! 偏好连接偏好连接 无标度网络的另一个特性，偏好连接，意 指新结点连接度高的结点的可能更大。 在如下的一个例子当中，新结点最有可能 和红色结点相连。 在现实生活中，新的网站很有可能会和一 些热门的网站相连例如Yahoo, Google, BaiDu。 New Node 幂分布现象。 无标度网络貌似服从幂分布。 早期的模型把网络描述成一个钟型曲线，大量的结点 拥有相同的度，而几乎没有高度的结点。 在无标度网络模型中，网络是由大量低度的结点以及 少量高度的结点所组成的。 # of

13、 links (k) # of links (k) # of nodes with k links # of nodes with k links Bell Curve Power Law Distribution BA 无标度模型 无标度模型由Albert-Lszl Barabsi和 Rka Albert在1999年首先提出，现实网络 的无标度特性源于众多网络所共有的两种 生成机制： （）网络通过增添新节点而连续扩 张； （）新节点择优连接到具有大量连 接的节点上。 BA模型 增长和择优连接这两种要素激励了BarabsiAlbert模 型的提出，该模型首次导出度分布按幂函数规律变化 的网络。

14、 模型的算法如下： （1）增长：开始于较少的节点数量（m0），在每个时间 间隔增添一个具有m（m0）条边的新节点，连接这个 新节点到m个不同的已经存在于系统中的节点上。 （2）择优连接：在选择新节点的连接点时，假设新节点 连接到节点i的概率取决于节点i的度数即 经过t时间间隔后，该算法程序产生一 具有N=t+m0个节点，mt条边的网络。 数量模拟表明具有k条边的节点的概率 服从指数为r=3的幂指数分布。 jj i i k k k )( P(k) k-3 A.-L.Barabsi, R. Albert, Science 286, 509 (1999) BA模型 （a)Barabsi-Albert模拟的度分布。 （b）不同系统规模下的 。 kp 300000 0 tmN 150000N100000N Degree Distribution Power-law distribution Scale-free Network Poisson distribut