巴拉巴西(Albert-László Barabási)与阿尔伯特(Réka Albert)提出的无标度网络模型。
模型提出
在此之前,大多数网络被想当然的认为是随机的,因此连接度分布可以近似用泊松分布来表示,而巴拉巴西与其学生阿尔伯特、郑浩雄通过对万维网度分布测量的结果却显示万维网度分布服从幂律分布,存在枢纽节点(拥有大量链接的节点)。也许万维网是特别的,巴拉巴西研究组进而又分析了两个网络系统——IBM计算机芯片布线图与好莱坞演员数据库,结果其度分布均遵循幂律分布。
为什么差异很大的万维网、计算机芯片、演员网络不同于随机网络反而拥有枢纽节点并服从幂律分布,为了回答这个问题巴拉巴西提出了区别于随机网络模型的两个要素生长和偏好连接,由此建立无标度模型,即BA模型。
生长(增长性):随机网络模型假设节点数目N是固定的。然而在真实的网络中,由于新节点的加入,节点的数目是不断增长的。
例如,互联网、交通网络、社交网络随着时间不断的扩增。
偏好连接(优先连接性):随机网络中节点随机地选择节点进行连接,而真实网络中,新节点倾向于和链接数高的节点相连。
例如,被引次数高的文章更有机会被阅读,受欢迎的同学更有机会被认识。
模型定义
初始时,网络中有m0个节点,这些节点任意连接,只需保证每个节点至少有一个链接即可,并按照生长与偏好连接逐步演变。
生长:每步向网络中添加一个拥有m(≤m0) 条链的新节点。
偏好连接:新节点每次在选择连接时,选择度为ki 的节点进行连接的概率为
[ki指节点i的度数]
经过t个时间步后,模型生长为网络节点数N=t+m0,链接数为m0+mt的网络。
特征
单个节点度随时间变化情况
新节点加入时,它会在网络中已经存在的N(t)个节点中选择m个与之连接,用一个连续实数变量来近似ki,该变量可以理解为ki在多次网络生长过程中的平均值。那么i节点获得新链接的速率可以写成:
系数m体现每个新节点会带来m个链接。因此,节点i有m次被选择的机会,求和项针对新节点外的所有节点进行。
因此有,此外当t步骤较大时,可以忽略,得到
对其积分,并考虑到ki(ti)=m(节点i在时刻ti加入网络)后有
称β为动态指数,取值为
推论:每个节点的度都依照幂律增长,并且有相同的动态指数β=1/2。因此,所有的节点遵循相同增长规律。
度的增长是亚线性的(β<1)。因此新节点加入网络时总有比它之前加入的节点更多的节点可以连接。
节点越早加入网络,它的度ki就越高。
BA模型度分布
BA模型所生成网络的显著特征是具有幂律度分布。目前对BA网络度分布的理论研究的方法主要有连续场理论,速率方程法,主方程法,得到的渐近结果都是相同的。
主方程法,定义p(k,ti,t)为ti时刻加入节点i在t时刻的度恰好是k的概率。在BA网络中当一个新节点加入系统时,节点i的度增加1的概率为mΠi =k/2t,否则该节点度保持不变。由此得到递推公式:
而BA无标度网络的度分布为:
它满足如下递推方程:
从而求得BA无标网络的度分布函数为
这表明BA无标度网络可有幂指数为3的幂律函数近似描述。
直径与聚类系数
m>1且N较大时,平均路径长度:
聚类系数:
BA模型局限
·该模型预测度指数为γ=3,而真是网络的度指数可以有更宽松取值(一般2到5间)。
·BA模型定义中有数学细节未指明包括初始M0个节点的连接情况;加入的节点新建的链是逐步的还是同时的,可能导致多重链接。
·万维网、引文网络等许多真实网络都是有向的,而BA模型生成的网络都是无向网络。
·网络中观测到的很多过程,例如节点间形成链接、链接消失、节点消失等,在BA模型中没有。
·BA模型是一个最较简化的、原理性的模型,其主要初衷是刻画无标度特性形成的基本机制,针对实际网络系统还有其他特性需要考虑,如有向性、节点的消失等。