从幂律分布到异速增长

来自集智百科
跳转到: 导航搜索

目录

有上下界的幂律分布

考虑一个幂律分布 
p(x) = C x^{-\alpha}

一般的分析里都只假设存在下界 
x_{min}
, 但这里我们同时还假设存在上界 
x_{max}
,

此时结合概率归一化条件 
\int^{x_{max}}_{x_{min}} p(x)\,dx = 1
可以得到 
C = \frac{1-\alpha}{{x_{max}}^{1-\alpha}-{x_{min}}^{1-\alpha}}

有上下界的Zipf's law

我们知道,Zipf's law其实是幂律分布的一种变形。变量x的降序r排列减去1可以看做含有N个元素的系统中比x大的元素的个数。即 
r-1 = (N-1) \int^{x_{max}}_{x(r)} p(x)\,dx 
, 变形得到


x(r) = ((1-\frac{r-1}{N-1}) x_{max}^{1-\alpha}+\frac{r-1}{N-1}x_{min}^{1-\alpha}  )^{\frac{1}{1-\alpha}} 
,

我们平时说的Zipf's law,其实是这个函数在x_{min}=1, x_{max}=\infty时的特殊形式: 
x(r) = x_{max} r^{-\beta} = N^{\beta} r^{-\beta} 
, 其中
\beta=\frac {1}{\alpha-1}


k = \frac{r}{N} 
为归一化后的降序,则有 
x(r) = ((1-k) x_{max}^{1-\alpha}+k x_{min}^{1-\alpha}  )^{-\frac{1}{\alpha-1}} 
,

Zipf law with broundary.png 24hour.png

上图的示例数据中纵轴为“穿越火线吧”(日PV排名22)一个小时的点击流网络中节点流量Ti和耗散量Di的分布。最右边的图显示了24小时的情况。横轴是归一化后的降序排列k。变量下界是1。斜率是\beta。拟合得到\beta1=1.39\beta2=0.77。可以看出,考虑变量上界的拟合(红线实线)要比不考虑上界的拟合(紫色虚线)效果好,虽然两者给出的斜率\beta是一样的(因为变量值比较小的数据点占大多数,所以一小部分变量值大的数据点偏离理论曲线并不会改变对斜率的估计)。


其实上图中的例子并不特殊。许多时候Zipf'a law在真实数据中都不是一条直线,而是在变量取值比较大的地方偏离理论预测曲线。为什么会这样呢?这和幂律分布抽样的特殊性有关。假设样本是从一个下界为1,上界为无穷大,幂指数为\alpha的幂律分布中取的,那么随着系统规模N增加,我们总要取得一个x_{max} =N^{\beta} = N^{\frac{1}{\alpha-1}}的最大值才可以得到一个呈现严格Zipf's law的样本。这个样本非常好地保持了总体的统计性质,使得我们可以从样本中把总体参数\alpha估计出来。但实际情形是,在一个如上假设的幂律分布中随机抽样,取到的最大值确实是随着样本规模N增大,但远远跟不上x_{max} = N^{\frac{1}{\alpha-1}}的速度。这就造成许多实际系统中的rank-ordered曲线总是“垂头丧气”,而不是挺直的Zipf' law 。研究城市的专家Batty等人在这篇文章中提出了类似的观点,和互联网系统不同,在城市人口数据里,往往还存在数据缺失导致下界未知的情况,即只有排名前若干的变量值。互联网数据往往是比较精确的,并不存在这样的数据缺失,因此可以假设样本是从总体中的随机抽样。但不论数据缺失与否,在不同系统中,样本在变量最大值附近偏离理论幂律分布的现象是同样普遍的。


以前的文献中也认识到了这个问题,但解决的方法比较ugly。比如加上一个指数下降来抑制变量取值,使得当x的值大到一定程度,概率p(x)迅速下降到接近0,其分布形式为p(x) \propto L(x) x^{-\alpha} \mathrm{e}^{-\lambda x}。但这种办法显然是不正确的。样本极大值和理论理论极大值之间的距离是可以根据统计理论来推测的,不必生硬地引入一个参数\lambda来解决。

Newzipf.png

新的Zipf law 
x(r) = (x_{max}^{1-\alpha}-\frac{(1-\alpha)N^{\eta}}{x_{max}}k  )^{-\frac{1}{\alpha-1}} =(x_{max}^{-1/\beta}+\frac{N^{\eta}}{\beta x_{max}}k  )^{-\beta}

p(x)=\frac{x_{max}}{N^{\eta}}x^{-\alpha}
推导而来,可采用最大似然来估计\beta\eta

从Zipf's law到Dissipation law

Beta gamma.png

左图为“穿越火线吧”一个小时的点击流网络中节点流量Ti和耗散量Di的相互关系。之前已经通过分布得到\beta_{T_i}=1.39\beta_{D_i}=0.77。那么\gamma的理论值应该有\gamma=\beta_{T_i}/\beta_{D_i}=0.55。实际拟合值为0.52。与理论预测值还是比较一致的。根据右图为1000个吧在24小时内平均的\beta_{T_i}/\beta_{D_i}\gamma的关系。可以看出,两者之间有很强的相关性。

幂律分布的随机样本的极大值的期望

理论分析

如果已知概率密度分布p(x),那么我们就可以得到从这个分布里得到的规模为N的随机样本的极大值的期望。其操作方法如下:

(1)写出累积概率分布F(x);

(2)极大值的累积概率分布H(y)即F(x)的N次方,因为我们要求连续抽N次得到的数值都小于y=x_{max}

(3)对F(y)做微分得到概率密度分布g(y);

(4)对y*g(y)做积分得到期望值E(y)。


好,让我们动手吧!


(1)写出累积概率分布F(x) = Pr{X<=x}

有概率分布p(x) = C x^{-\alpha},其中C = \frac{1-\alpha}{{x_{max}}^{1-\alpha}-{x_{min}}^{1-\alpha}}

因为现在讨论的是理想幂律分布,可以设定变量最小值x_{min}=1, 最大值x_{max}=\infty则有C=\alpha - 1 , 
F(x) = \int^{x}_{1} p(x)\,dx = 1-x^{1-\alpha}

(2)写出极大值的累积概率分布H(y)


H(y) = [F(y)]^N =  (1-y^{1-\alpha})^N

(3)得到概率密度分布g(y)


g(y) = \frac{d H(y)}{d y} = \frac{N(a-1)(1-y^{1-\alpha})^N}{y^\alpha-y}

(4)得到期望值E(y)

因为y是x的极大值,所以y_{min}=1y_{max}=\infty


E(y) = \int^{y_{max}}_{y_{min}} y \,g(y)\,dy = \int^{\infty}_{1} \frac{N(\alpha-1)(1-y^{1-\alpha})^N}{y^{\alpha-1}-1} \,dy = N(\alpha-1) \int^{\infty}_{1} y^{1-\alpha}(1-y^{1-\alpha})^{n-1} \,dy

数值模拟

Alpha and gamma1.png

上图中左图里我们在三个幂律分布中抽样,参数\alpha分别为1.5(蓝色), 2(紫色), 2.5(红色)。横轴是样本规模,在10^2到10^4之间波动,纵轴是样本最大值的平均值。每一个数据点都由200次随机抽样结果加以平均得到。可以看出,存在幂律关系E(y)\sim N^{\eta},而且其幂指数\eta(拟合线斜率)是与\alpha负相关的。

右图中我们考察了\beta是如何随着\alpha变化的。从上图中我们看到,它们之间关系完全符合Zipf's law预测的那样\eta=\beta=\frac {1}{\alpha-1}(红线)。

实证数据

Beta eta.png

左图是对“穿越火线”(日PV排名22)吧在一天内24个点击网络的分析,发现Di和Ti的最大值与节点数量N存在幂律关系E(y)\sim N^{\eta}\eta_{T_{i}=1.20},\eta_{D_{i}=1.16}。之前我们已经估计得到\beta_{T_{i}=1.39},\beta_{D_{i}=0.77},可见\beta\eta并不一致。右图是对1000个吧在24小时内的\eta\beta关系的分析(数据点经过均值合并处理),发现前者总是大于后者(灰色虚线斜率为1,因此数据点在线的上方表明y轴坐标大于x轴坐标)。


与之前的模拟结果相比,我们发现变量的最大值长得比Zipf's law所预测的速度N^{\beta}=N^{\frac{1}{\alpha-1}}快。实际速度为N^{\eta}。这是一个悬而未决的重要问题。这也是出现异速增长的根本原因,因为异速增长的指数为\theta=1+\eta-\beta,如果\eta\beta相等,就不会出现异速增长了。

从Zipf's law和dissipation law到异速增长

Allometry.png

左图是对“穿越火线”吧在一天内24个点击网络的分析,发现节点(帖子)数量N,用户数量UV,和点击量PV之间存在幂律关系,幂指数分别为\theta1,\theta2,和\theta3

Eta beta theta1.png

对一千个吧在24小时内的异速增长关系进行分析,发现使用Di和Ti的分布参数\eta,\beta可以有效预测\theta1,\theta2,和\theta3

最终结果

Final-lingfei.png

个人工具
名字空间
操作
导航
工具箱