节点度分布p(k)p(k)为关于kk的函数,表示网络中度为kk的节点占多大比例。我们发现,现实世界许多网络的节点度分布与幂函数乘正比:
p(k)∝k−αp(k)∝k−α由于对y=x−αy=x−α两边取对数可以得到log(y)=−αlog(x)log(y)=−αlog(x),因此我们使用原数据在log-log尺度
可以看到此时幂律分布像一条斜率为−α−α的直线。事实上,我们可以用该方法快速检测一个数据集是否服从幂律分布。像与幂律分布p(k)∝exp(−k)p(k)∝exp(−k)和指数分布p(k)∝k−αp(k)∝k−α就可以使用取对数的方法进行区分,因为对y=f(x)=e−xy=f(x)=e−x两边取对数我们得到的是log(y)=−xlog(y)=−x。
我们继续看在原始坐标轴下到
我们再来看一下现实生活中的幂律分布和其它分布的对比。事实上,航空网络的度分布常常满足幂律分布;而高速公路网络的度分布则常常满足泊松分布(指数族分布的一种),其均值为平均度k¯k¯。它们的对比
如果分布p(x)p(x)对应的互补累计分布函数(complementary cumulative distribution function,CCDF)P(X>x)P(X>x)满足:
limx→∞P(X>x)e−λx=∞limx→∞P(X>x)e−λx=∞
则我们称分布p(x)p(x)是重尾分布(heavy tailed distribution)。
幂律分布就是一种典型的重尾分布(就像我们前面所展示的节点度高度倾斜)。但需要注意的事,以下分布不是重尾分布:
事实上,重尾分布有着不同的变种和形式,包括:长尾分布(long tailed distribution),齐夫定律(Zipf's law),帕累托定律(Pareto law,也就是所谓的“二八法则”)等。
对于重尾分布而言,其概率密度函数p(x)p(x)正比于:
接下来我们考虑幂律分布
p(x)=Zx−αp(x)=Zx−α
的归一化常数ZZ应该怎么取。由于要让p(x)p(x)是一个概率分布的话则需要满足:∫p(x)dx=1∫p(x)dx=1。由于p(x)p(x)在x→0x→0的时候是发散的,我们取一个最小值xmxm,接着我们有:
1=∫∞xmp(x)dx=Z∫∞xmx−αdx=−Zα−1[x−α+1]∞xm=−Zα−1[∞1−α−x1−αm]1=∫xm∞p(x)dx=Z∫xm∞x−αdx=−Zα−1[x−α+1]xm∞=−Zα−1[∞1−α−xm1−α]
当α>1α>1时,我们有Z=(α−1)xα−1mZ=(α−1)xmα−1。于是,可以得到归一化后的幂律分布形式:
p(x)=α−1xm(xxm)−αp(x)=α−1xm(xxm)−α
幂律分布随机变量XX的期望值
E[X]=∫∞xmxp(x)dx=Z∫∞xmx−α+1dx=Z2−α[x2−α]∞xm=(α−1)xα−1m−(α−2)[∞2−α−x2−αm]E[X]=∫xm∞xp(x)dx=Z∫xm∞x−α+1dx=Z2−α[x2−α]xm∞=(α−1)xmα−1−(α−2)[∞2−α−xm2−α]
当α>2α>2时,我们有
E[X]=α−1α−2xmE[X]=α−1α−2xm
若α≤2α≤2,则E[X]=∞E[X]=∞,若α≤3α≤3,则Var[X]=∞Var[X]=∞。事实上当方差太大时均值就没有意义了。
在真实的网络中2<α<32<α<3,所以E[X]=constE[X]=const,Var[X]=∞Var[X]=∞。
为了印证我们上面的理论,我们通过实验模拟当幂律分布的指数αα的取不同值时,从分布中所采的nn个样本的均值和方差随着n→∞n→∞的变化情况
可以看到,和我们上面的理论符合
网络度分布遵循幂律分布的网络我们称为无标度(scale-free)网络(也称无尺度网络)。所谓无标度,其实来源于统计物理学里的相转移理论(事实上统计物理和复杂系统联系紧密)。网络一阶矩是平均度,二阶矩是度的方差。我们在博客《图数据挖掘:Erdos-Renyi随机图的生成方式及其特性》中说过,ER随机网络的平均度k¯k¯与度方差σ2σ2都是可以估计的,这就是所谓“有标度”。但正如我们前面所分析的,在幂律分布网络中,方差和期望都可能不存在,这也是Barabási等人将其称为“无标度”的原因[2][3]。
我们下面展示了随机网络(Erdos-Eenyi随机图)和无标度网络的对比
网络的弹性(resilience)意为网络对攻击的抵抗能力,而这可以通过网络的一些度量属性随攻击的变化来体现。
节点的移除方式包括两种:
网络的弹性分析对互联网的鲁棒性和流行病学都非常重要。接下来我们就来看几种经典网络类型的弹性分析实验。我们采取的度量属性包括: