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

(1) 如果典型节点u的链路没有重联，它的度不变；若其它节点链路重定向到

u时，度会增加。

(2) 不重联链路的概率服从二项式分布B?k,i,?1?p??，这里k?m/n,i?不重联

的链路数，p为重联概率。

(3) 其它节点链路重联到节点u的概率服从泊松分布P??1,d?k?i??d?k?，其

中，?1?pk是重定向链路的期望值，d=度数，i=重联到u的链路数。 (4) 节点u度数增加的概率等于联合概率B?k,i,?1?p??P??1,d?k?i?。 (5) 度分布h?d?等于在i?1,2,3,...,min?d?k,k?条链路上的联合概的总和。 因此，重联后具有d条链路的节点度分布：

min?d?k,k?h?d??其中，

?i?1B?k,i,?1?p??P??1,d?k?i?;d?k

?1?pk

B?k,i,?1?p????ik??1?p?pk?i

iP??1,d?k?i???pk?d?k?ie?pk?d?k?i?!

下图3-6给出当n=50,m=400和重联概率p=50%时的随机网络和小世界网络度序列分布：

图3-6 小世界网络度序列分布

23

3.4.4 小世界网络属性

小世界具有相对小的平均路径长度、高的聚集系数和可以调整的熵（根据重联概率p变化）。当p＝0时，平均聚集系数：C?3?K?2?4?K?1?，这里我们用大写的K

表示小世界模型对应的规则网中每个节点的常数度值。在0?p?1时，对于任一个节点，它的两个邻点仍旧是它的邻点的概率分别都是(1-p)，它们之间也邻接的概率也是(1-p)，因此小世界模型的平均聚集系数的期望值为：

C?3?K?2?4?K?1??1?p?3，

与N无关。当然，这只是一个近似估计。

小世界模型的平均距离解析计算曾经是一个比较困难，因而引起热烈讨论的问题，目前大家普遍接受的是纽曼(Newman)、穆尔(Moore)和瓦兹(Watts)用平均场方法得到的解析表示式[1]：

N1/dl?N,p??f?pKN?，

K??常数若u?1??4u??tanh?1若u?1? 其中：f?u???2u2?4u?u?4u若u?1??ln?u?/u???由此公式不容易看出平均距离对N的依赖关系。Watts和Strogatz定量地显示了平均聚集系数和平均距离对N的依赖关系，如图3-7所示：

24

图3-7 小世界模型平均聚集系数以及平均距离对N的依赖关系[6] 图3-7中C?0?和L?0?分别表示小世界模型对应的规则网中的平均聚集系数和平均距离，C?p?和L?p?分别表示小世界模型中的平均聚集系数和平均距离。

WS模型中，可以发现这样一个特点：图中显示当p从零增加时，产生的少数随机跳跃边，所有节点之间的平均距离会大大降低，而增加的链接又不会太大地改变网络的聚集系数。这一特性说明人们在交友的时候，范围可能有限，但只要其中有少数人交往广泛、活跃，拥有远距离的链接，社会就能构成小世界。从这个模型可以看出，“六度分隔”是植根于人群中有少数人的亲朋好友住在远处，而不是左邻右舍。因此，对于大规模的网络而言，无须充满随机链接，只需要少数几个远程链接，就能显示出“小世界”的特性。

3.5 基于平均场的无尺度网络BA模型

许多网络统计性质，度分布是反映网络拓扑结构最基本也是最重要的性质。一个网络节点直接连接邻点的数目，在一定程度上表示它在网络中的重要性。例如电影演员、科研人员合作网中，节点度基本上描述了一个节点获得合作成果（影片或论文）的多少，也就是他们在合作中的地位重要程度；交通网中，节点度描述了一个节点在网中的“枢纽”程度等等。规则网络的度分布是?函数，即所有节点的度完全相同，或者分为有限组，每组内全相同；从随机网络和小世界网络节点分布度来看，当节点度k等于其数字期望时，其相应的概率达到最大值，而当 或 时，其概率按指数级减小。因此，随机网络和小世界网络节点度的分布区间很狭窄，几乎找不到偏离节点度均值较大的点，表现出节点分布的“均质性”。

1999 年，美国物理学家巴拉巴西（Barabási）和阿尔波特（Albert）在Science 上发表的论文[14]，提出了一种无尺度(scare-free)网络模型，并举出例子来说明许多实际网络都具有所谓的“无尺度性”。 3.5.1 无尺度(scare-free)网络

过去的几年中，不同领域的研究者发现，很多网络都是由少数一些具有众多连结的节点所支配的，包括万维网、细胞代谢系统，以及好莱坞的演员网络在内。包含这种中心节点(或称集散节点)的网络，我们通常称之为“无尺度”(scale-free)网络。

25

图3-8 随机网络与无尺度网络对比[12]

随机网络可以用美国高速公路为代表（图3-8左上），其中包含一些节点和随机布置的连接。在这类网络中，节点连接的分布将服从钟形分布（图3-8左下）。这种分布中，大部分节点带有相当数目的连接。与之相反，美国航空网则是无尺度网络的代表（图3-8右上），它存在大量连接的中心节点。在这种网络中，节点与节点之间的连接分布遵循幂律分布（图3-8右下），其中大部分节点只有少数连接，而少数节点则拥有大量的连接。这种系统的定义特性是，在双对数坐标中，节点度分布是一条直线，斜率即幂指数。

以上分析，对于无尺度网络，它近似地显示遵循幂函数的度分布。说明实际复杂网络中节点重要程度的分布是强烈“异质性”的。

均质常常意味着均匀、平衡、无序，而异质常常意味着不均匀、非平衡有序。我们周围丰富多彩的世界正是无处不在的不均匀、非平衡、复杂而有序造成的。“实际复杂网络中基本单元度分布的无尺度性”显示了各个基本单元的“重要性”或“作用”非常不相同。在人群中像爱因斯坦那样的优秀人物是极少数；在食物链中像狮子、老虎那样的“顶端生物”也一定是极少数。而该群体中极大多数远远谈不上“优秀”，但却是支撑他们的基础。这些层次、组织等特征正是复杂性的一种体现。

下图3-9显示了万维网、路由器层次的因特网、电影演员合作网、高能物理学家科研合作网和神经科学家合作网的度分布，它们都精确或近似地遵循“幂律”。

26

图3-9 （左）万维网的(a)出度；(b)入度分布；（右）(a)路由器层次的因特网；(b)电影演员合作网；(c)高能物理学家科研合作网；(d)神经科学家合作网的度分布[6] 3.5.2 无尺度(scare-free)网络BA模型

Barabási和Albert研究了包括WWW在内的大型网络拓扑[2]，发现这样一个规律：决定真实网络演化的两个基本因素是增长性和偏好连接。这也是前面所提到的随机网络ER模型和小世界网络WS模型所没有考虑的两个重要因素。首先，网络演化过程中，网络节点数不可能一成不变，它有一个增长的过程；另外，对于新加入节点，该节点与其它节点的连接概率并不是相同的，而Barabási和Albert提出的“偏好连接”，定义其与其它旧节点连接概率跟旧节点的度成正比。这两个因素在网络演化中，导致节点度序列分布呈现幂律分布。

1999年，他们提出了无尺度网络的演化模型，即BA模型。BA模型的核心思想是“富者通吃”的竞争法则，这种演化趋势，使得度大的节点会越来越大，而度小的节点呈现出普遍性，结果演化成极少数节点有大量的连接，而大多数节点只有少量连接。这类似于社会学中的“马太效应”或者“名人效应”，而这种通过中心节点的松散联系而聚合的“集群现象”普遍存在于各种真实的网络中。

无尺度网络生成过程通过从网络G的度序列分布中以时间步t取样创建动态网络。其生成过程如下：

(1) 增长性：从少数的节点开始，设为m0，对于每一个时间步长，增加一个新节点到网络中，且该节点带有m?m?m0?条链路，这些链路将连接到网络中原有的节点上。

27

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