平均场理论在计算机网络中的应用研究 - 图文(9)

(2) 偏好连接：新添加节点与其它旧节点i的连接概率与旧节点度（连通性）ki成正比，可以得到：

P?ki??ki/?kj

j经过时间步t后，该网络节点数N?m0?t，总链接数n?mt，所有节点度之和

?kjj?2mt。

偏好连接是无尺度网络的主要特色。偏好连接最早被定义成“累积优势”

(Price,1965,1976)，它的产生来自网络科学在增长现象中的应用。它是一个在不同研究领域具有不同名字的概念。偏好连接在经济学中称为报酬增加律(law of increasing returns)，在人工智能中称为适应性学习(adaptive learning)，在生物学中称为自然选择(natural selection)。偏好连接是一种正反馈，从而表现“穷者愈穷，富者愈富”的演化趋势。

图3-10表示了m0?3，m?2的无尺度网络的简单演化过程：

t=0t=2t=3

图3-10 无尺度网络演化过程

在t?0时，网络中存在着m0?3个孤立的节点。在每一个时间步长，网络中新加入带有m?2条链接的一个节点，该节点具有偏好连接性。因此，在t?0时，网络中节点数为m0?t?5，链接数为mt?4。在t?3时，加入第6个节点，虚线表示了该新节点与网络中其它节点的链接情况，其连接遵循偏好连接性，即优先连接高连通性的节点。

3.5.3 BA模型节点度序列分布及平均场解析

Barabási和Albert提出的无尺度网模型包括两个要素：增长性和偏好连接。前者强调复杂网络是一个开放系统，新的基本单元不断加入，节点总数在不断增加；后者强调节点连接新边的概率应该单调依赖于它已经有的度，即所谓“富者更富”

28

法则。这两条无疑是符合实际的。任何实际复杂系统一定不是理想孤立，而已经掌握大量财富的人一定比穷小子更容易赚钱。BA模型即在这两条原则基础上进行演化，直到达到一个稳定演化状态。

Barabási和Albert的数值模拟说明在t够大时模型产生的网络会达到一个稳定演化状态，这时度分布遵循幂律分布。

对于一个具体细节依赖于随机因素的动力学过程，平均场方法的思想就是抛开

这些具体细节，仅仅考虑全局的、平均的动力学效果。在许多情况下，可以把某些动力学现象的发生概率近似为常参量，列出微分方程形式的平均场方程。它们可以用大家熟悉的微分方程解法来求解，但是并不代表还原论方法论框架下的系统动力学机制。根据这种思想，令ki(t)表示在t时间步长节点i的度数，把ki(t)看作连续动力学函数。每时间间隔增加的连接数为m，即?k?m。考虑t时刻

?kj?2mt?m，在t够大时近似有

j?kiki?。从而得到无尺度网络演化模型的平?t2t均场方程为：

?kikiki?A?(ki)?A? ?t?kj2tj在初始条件下，新加入的节点带入m条边，则节点i在ti时间步长加入到网络

1?t?中的连通性为ki?ti??m，令A?m，从而解方程得ki?t??m??，其中??称为

2?i?动力学指数，即所有节点的度都以幂函数形式增加，但是同一时刻达到的度值不同，且在t够大时达到度序列分布遵循幂律分布的稳定演化状态。

在实际问题中，当我们无法区分在区间?a,b?内取值的随机变量X取不同值的可能性有何不同时，我们就可以假定X服从?a,b?上的均匀分布。这里，假设网络在相同的时间间隔，增加一个新的节点，则该时间步长ti可以看成服从均匀分布的随机变量，故有：

P?ti??1，与ti无关。 m0?t?于是，由动力学方程解，网络度序列分布可以推导如下：

由偏好连接中“富者愈富”的演化趋势，可令k?ti??k，可得

29

?t?m2t???k/m?ti?2

k?ti??从而得出一个节点连通性k?ti??k的概率分布函数为：

m2tm2tm2tP{ki(t)?k}?P{ti?2}?1?P{ti?2}?1?2kkk(m0?t)

则有节点度序列概率密度分布函数近似为： ?P{ki(t)?k}t P(k,t)??2m2k?3?km0?t再令t??，因此得到网络稳定度序列分布的概率密度函数近似为：

P(k)?limP(k,t)?2m2k??

t??其中??1??1??3（注意??1），?称为度序列（分布）指数，与m无关。注意：2尽管?2m2k?3dk?1，因为稳定度序列分布的概率密度函数只是离散概率的近似，

m对小度数会有较大的偏差。

Barabási和Albert还计算了如果网络照样增长，但是连接旧点是完全随机的，

可以类似地列出平均场方程为[14]：

?kim? ?tm0?t?1可以类似地解出：P(k)?e?k/m，即度序列分布遵循指数函数分布。 3.5.4 无尺度网络BA模型其它最主要统计性质

(1)hub:无尺度网络的hub是一个具有最大度的节点。hub度与刻度的对数成比例，即degree(hub)?log2(density)。

(2)熵：规范的无尺度网络的熵接近于：

?n?1?1.16145?log2?2??n?,2?m?n?1 I(scale?free)??n?1???n不过，在密度接近100%时，熵会急剧下降成0，因为网络在此时变成了完全连通的网络，而不是无尺度网络。

30

(3)平均距离：对于稀疏的无尺度网络的平均距离小于稀疏随机网络的平均距离。可以导出稀疏网络平均距离可以表示成：

??log?n?O??log?n??log?density??? ??密度大于，但是小于20%。Bollobas和Riordan宣称使用双对数近似可以更好地近似更符合实际的网络，如互联网

：

?log?n??avg_path_length(scare?free)?O???log?log?n??? ??比较规则网、随机网、小世界网，随着网络尺寸N的增加，规则网的平均距离增加最快，无尺度模型增加最慢，随机网居于中间，而小世界网又居于规则网络和随机网之间。因此，如果只考虑平均距离如何随N变化，无尺度网络并不居于规则网络与随机网络之间。这表明，好的模型并不一定包罗万象，反之，它们常常针对实际系统一个重要规律做出阐述。

(4)聚集系数：无尺度网络的聚集系数与网络的规模n成反比，随着密度线性地增长：CC(scare?free)?O(density)。Barabási宣称对于BA生成的无尺度网络来说，并不存在聚集系数解析近似解，但是有一个近似的表达：

CC(scare?free)?O(n?0.75)。

因为无尺度网络的密度近似于d?2??m/n?，聚集系数也随着?m的增长而增加：CC(scare?free)?O(?m)。单个节点的聚集系数与稀疏无尺度网络中节点的度成反比；对于较小的?m来说，聚集系数受限于CC(scare?free)?O(?m)。

随着网络尺寸的增加，规则网络的平均聚集系数完全不变化，衰减最慢；随机网络衰减最快；无尺度模型居于中间，而小世界网络又居于规则网络和无尺度网络模型之间。

人们对网络的日渐依赖，凸显了一个广受关注的问题：网络可靠性。对于复杂网络，其对意外故障的承受能力呈现一个较高水平。事实上，虽然网络上，每时每刻都有数百个路由器失效，但因特网却很少因此受到大的影响。

然后，我们的直觉是，如果大部分节点发生瘫痪，将不可避免地导致网络的分裂。对随机网络而言，这是绝对正确的：若将随机网络中较大部分的节点去除，网络必然溃散成彼此无法通讯的小型孤岛。而无尺度网络却由于其幂律分布，表现出对意外故障具有惊人的强韧性，这一特性本质上源于这些网络的非同质拓扑

31

结构：随机去除的方式所破坏的主要是那些不重要的节点，而这些节点数目远远大于中心节点，且这些节点对外连接并不多，因而去除它们不会对网络拓扑结构产生重大的影响。

3.6 本章小节

本章主要介绍了平均场理论的基本思想以及平均场理论在计算机网络中应用范畴；研究了网络科学的发展史，从网络拓扑结构的角度，对规则网络、随机网络、小世界网络以及无尺度网络的拓扑结构以及其它统计特性如平均距离、聚集系数等进行了深入探究，其中，随机网络和小世界网络网络拓扑服从一个泊松分布，而无尺度网络拓扑服从一个幂律分布。

针对不同的网络拓扑，建立起相应的网络模型，分别是随机网络ER模型、小世界网络WS模型以及无尺度网络BA模型。其中，本章通过平均场理论中的微分方程，对无尺度网络BA模型的建立过程进行了详细的解析计算，得出了无尺度网络幂律分布的理论参数。

最后，本章还分析了无尺度网络的安全性，即对中心节点的依赖性以及较强的网络可靠性。

其网络拓扑及统计特性对比如下表：

表2-1 网络模型对比

网络类型 网络参数 平均距离 聚集系数 节点分布 随机网络 大 大 Poisson分布 小世界网络 小 大 Poisson分布 无尺度网络 小 小 幂律分布 Internet 小 小 幂律分布

32

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库平均场理论在计算机网络中的应用研究 - 图文(9)在线全文阅读。