度分布：度分布是网络的一个重要统计特征。这里的度（Degree）也称为连通度（Connectivity），节点的度指的是与该节点连接的边数。对网络中所有节点的度求平均，可得到网络的平均度＜k＞。度分布则表示节点度的概率分布函数
P(k)，它指的是节点有k条边连接的概率。
2．小世界网络模型及其模拟
1929 年，匈牙利作家 F.Karinthy 最早提出了“小世界现象”的论断。他认为，在地球上的任何两个人都可以平均通过一条由六位联系人组成的链条而联系起来。而后，在1967 年，美国哈佛大学社会心理学教授Milgram 通过设计一个连锁信件实验，提出了著名的“六度分离”假说，即“小世界现象”[1]。这体现了一个似乎很普遍的规律：在如今的信息化时代，人们之间的关系已经完全社会化，任何两位素不相识的人都可能通过“六度空间”产生必然联系或关联。这一现象表明，在看似庞大的网络中各要素之间的间隔实际上是非常“近”的，大家在世界上通过一步一步的社会相识寻找到目标的这个短链子理论普遍存在于各种社会、经济网络中，科学家们把这种现象称为小世界效应[1]（Small-world effect）。为了用网络图来解释“六度分离”的小世界效应，，Watts 和 Strogatz在对规则网络和随机网络理论研究的基础上，于 1998 年提出了著名的 WS 小世界网络[1]。WS模型提出后，很多学者在此基础作了近一步改进，其中应用最多的是Newman和Watts提出的所谓NW小世界模型。事实上，当p很小N很大的时候，这两个模型理论分析的结果是相同的，现在我们统称它们为小世界模型。
前面我们已经简单的介绍了一下小世界网络的WS和NW模型，下面将着重介绍小世界网络的ws模型的特点。 2.1．WS 模型构造算法
1998年, Watts和Strogatz 提出了小世界网络这一概念,并建立了WS模型
[1]
。 实证结果表明,大多数的真实网络都具有小世界特性(较小的最短路径) 和
聚类特性(较大的聚类系数) 。 传统的规则最近邻耦合网络具有高聚类的特性,但并不具有小世界特性;而ER 随机网络具有小世界特性但却没有高聚类特性。 因此这两种传统的网络模型都不能很好的来表示实际的真实网络。 Watts和Strogatz建立的WS小世界网络模型就介于这两种网络之间,同时具有小世界特
5
性和聚类特性,可以很好的来表示真实网络[1]。
WS 网络模型同时具有平均路径长度短集群系数高的特点，但是，它的度分布仍是一个轻尾的Poisson 分布，而且WS 网络中不存在具有大量连接边的中枢点，因此，它仍然是一个平衡网络。近年来，研究人员对小世界网络得结构性质和动力学行为进行了深入的探索，取得了丰富成果。研究表明小世界网络能够增强信号的传播速度、提高计、提高计算能力和网络同步能力[8]。特别地，传染性疾病在小世界网络中传播要比在规则网络中容易得多。
WS 模型的生成算法为：给定一个具有N 个结点的环形网络规则，每一个结点对称地与它最近的m(m< 1、从规则图开始：考虑一个含有N个点的最近邻耦合网络，它们围成一个环，其中每个节点都与它左右相邻的各K/2节点相连，K是偶数。 2、随机化重连：以概率p随机地重新连接网络中的每个边，即将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点。其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与自身相连。在上述模型中，p=0对应于完全规则网络，p=1则对应于完全随机网络，通过调节p的值就可以控制从完全规则网络到完全随机网络的过渡。网络图像如下 ： 图3不同概率下网络示意图 网络图中各节点度的概率分布如下： 6 图4不同概率下各节点度的概率分布图 上面P=0.2时网络图显示，大部分连边保持不变，出现了少量捷径，正是由于这少量捷径造成了网络的小世界效应。 3.无标度网络模型及其模拟 1999年，Alber和Barabds发现WWW 网页的度分布不是通常认为的Poisson分布，而是重尾特征的幂律分布，而且WWW 基本上是由少数具有大量超链接的网页串连起来的，绝大部分网页的链接很少，他们把网络的这个特性称为无标度性[3](Scale-free nature，SF)。研究人员对大量的实际网络进行了实证分析，发现许多网络的度分布都是幂律的，要描述这些网络的结构和演化过程，随机图模型和小世界网络模型显然无能为力。 1999年Barabdsi和Albert考察了实际网络的生成机制，发现增长和择优连接是实际网络演化过程的两个基本要素，他们创造性地构建了能够产生无标度特性的第一个网络模型——BA模型[6]。BA模型的生成算法如下： (1)增长：网络开始于少数几个结点(m0个)，每个相等时问间隔增加一个新点，新点与m(≤m0)个不同的已经存在于网络中的旧点相连产生m条新边。 (2)择优连接：假设新点与旧点i相连的概率p取决于结点i的度数ki，即 ki? p（ki） （4） ?ikj经过t步时间步后，BA模型演化成一个具有N=t+m0个结点mt条边的网络。 BA网络主要具有以下特性：具有幂律度分布，是一个无标度网络；具有小 7 世界特征。幂律度分布的重尾特征导致无标度网络中有少数具有大量连接边的中枢点，择优连接必然产生“富者愈富”现象。BA 网络同时具有鲁棒性和脆弱性，面对结点的随机失效，网络具有鲁棒性；但面对蓄意攻击时，由于中枢点的存在，网络变得十分脆弱，很容易陷于瘫痪[9]。 3.1. 无标度网络模型构造算法 按照BA模型的定义，针对Matlab语言的特点，以初始节点等于3为例，设计如下算法[11]： 第1：生成m0=3个结点的初始完全网络，设置网络规模为N(m0)，并用Matlab特有的稀疏矩阵处理函数。 第2：每隔一个固定时段加入一个新的结点，按照概率p(ki)与原有网络结点产生m条无重复连边，重复上述过程N-m0次； 第3：存储N=100个结点的网络邻接矩阵。下面分别就N=10、N=60、N=100、 做图： 图5无标度网络生成的演化图 上面三幅图对应的网络图中各节点度的概率分布如下： 图6节点数不同时各节点度的概率分布图 8 上面组图显示，大部分结点的连边较少，少数结点具有大量的连边，这些具有大量连边的结点构成了网络的中枢点。当结点个数无限增加时，网络结点的度分布为幂律分布，可以用幂律形式P（k）∝k?γ即P（k）=ak?γ网络即为无标度网络。转换为对数函数：lnP（k）=lna-?lnk令lnP为y，k为x则y=lna-?x，当 ?=2，a=1时函数图如下： 图7各节点度的概率分布双对数曲线 许多实际大规模无标度网络，其幂指数通常为2≤γ≤3，绝大多数节点的度相对很低，也存在少量度值相对很高的节点，把这类网络称为无标度网络。 4. 结语 现实世界中许许多多的复杂网络都是具有小世界或无尺度特征的复杂网络，从生物体中的大脑结构到各种新陈代谢网络,从Internet到WWW,从大型电力网络到全球交通网络,从科研合作网络到各种政治、经济、社会关系网络等等,数不胜数。因此，对小世界网络和无标度网络及其模型进行更深入的研究是非常必要的。 参考文献 [1] Watts, D.J. and Strogatz, S.H. Collective dynamics of “small world” networks. Nature,393, 440-442,（1998） [2] Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the internet topology[C]//ACM SIGCOMM Computer Communication Review. ACM, 1999, 29(4): 251-262. [3] Albert R, Barabasi A.L.，Statistical mechanics of complex networks[J]. Reviews of Modern Physics 74, 47-97 (2002) [4] Newman M.E, Watts D.J. Renormalization group analysis of the small-world networkmodel[J]. Physics Letters A263，341–346（1999） 9