无标度网络
1.简介
传统的随机网络(如 ER 模型),尽管连接是随机设置的,但大部分节点
的连接数目会大致相同,即节点的分布方式遵循钟形的泊松分布,有一个特征
性的“平均数”。连接数目比平均数高许多或低许多的节点都极少,随着连接数
的增大,其概率呈指数式迅速递减。故随机网络亦称指数网络。
现实世界的网络大部分都不是随机网络,少数的节点往往拥有大量的连接 ,
而大部分节点却很少,一般而言他们符合 zipf 定律,(也就是 80/20 马太定律)。
人们给具有这种性质的网络起了一个特别的名字——无标度网络。这里的无标
度是指网络缺乏一个特征度值(或平均度值),即节点度值的波动范围相当大。
现实中的交通网,电话网和 Internet 都是无标度网络,在这种网络中,存
在拥有大量连接的集散节点。分布满足幂律的无标度网络还具有一个奇特的性
质—“小世界”特性。虽然万维网中的页面数已超过 80 亿,但平均来说,在万维
网上只需点击 19 次超链接,就可从一个网页到达任一其它页面。
无标度网络具有严重的异质性,其各节点之间的连接状况(度数)具有严
重的不均匀分布性:网络中少数称之为 Hub 点的节点拥有极其多的连接,而大
多数节点只有很少量的连接。少数 Hub 点对无标度网络的运行起着主导的作用。
从广义上说,无标度网络的无标度性是描述大量复杂系统整体上严重不均匀分
布的一种内在性质。
1999 年, Albert、Jeong 和 Barabs 发现万维网网页的度分布不是通常认
为的 Poisson 分布,而是重尾特征的幂律分布,而且万维网基本上是由少数具有
大量超链接的网页串连起来的, 绝大部分网页的链接很少,他们把网络的这个特
性称为无标度性(Scale-free nature, SF)。1999 年 Barabs 和 Albert 考察了
实际网络的生成机制, 发现增长和择优连接是实际网络演化过程的两个基本要
素, 他们创造性地构建了能够产生无标度特性的第一个网络模型——BA 模型。
BA 网络主要具有以下特性: 具有幂律度分布, 是一个无标度网络; 具有小
世界特征。幂律度分布的重尾特征导致无标度网络中有少数具有大量连接边的
中枢点, 择优连接必然产生“富者愈富”的现象。BA 网络同时具有鲁棒性和脆弱
性,面对结点的随机失效, 网络具有鲁棒性;但面对蓄意攻击时, 由于中枢点的
存在, 网络变得十分脆弱, 很容易陷于瘫痪。
特别地, 网络传染性疾病在无标度网络中不存在传播阈值, 疾病一旦产生就
在网络上迅速传播并达到稳定状态。如果没有人为干预, 疾病将在网络中永远
存在, 不会自动灭绝。这对制定无标度网络上的网络疾病防控策略提出了重大
挑战。
2.BA无标度网络构成原则
( 1) 增长: 网络开始于少数几个结点(初始设定为m0个) , 每个相等时间间
隔增加一个新点, 新点与m个(m小于等于m0)不同的已经存在于网络中的旧点
相连产生m条新边。
(2)择优连接:新点与旧点i相连的概率P取决于结点i的度数ki。