幂律分布与Zipf's Law

heyeshuang (53)in #cn • 7 years ago

前几天读了《复杂》。对复杂学的研究，在人工智能重获热度的今天，似乎获得了新的意义——当然，我们还是不知道炼金术的大锅里面发生了什么。

幂律分布/Zipf定律/帕累托法则/80-20定律/whatever，本质上是同一种东西。这种分布模式和正态分布类似，广泛存在于大自然和人造物的各个角落。一般来说，对于具有：

优先连接性（Preferential attachment）/马太效应
- “凡有的，还要加给他，叫他有余；没有的，连他所有的也要夺过来。”
成长性
- 网络的尺度不受客观条件的限制，可以无限增长

的网络，其节点连接数较为满足幂律分布。

Youtube上有个视频对幂律分布讲得很清楚，对其中提到的两个实验，我利用python进行了模拟。模拟中使用的jupyter notebook文件放在了github gist上。

猴子和打字机

一只猴子（我们叫它Shashi Biya）在打字机上乱敲，它敲二十六个字母和空格概率都相等。那么，咱们能不能看出他的用词习惯？答案是肯定的。

import string,random
from collections import Counter
s=string.ascii_lowercase+" "
s="abcd "
monkey=''.join(random.choices(s, k=10000000))
monkey=[m for m in monkey.split(" ") if m]
c=Counter(monkey)
common=c.most_common()[:10000]
fre=[value for (key,value) in common]
plt.plot(fre)
plt.xscale('log')
plt.yscale('log')
plt.show()

我们的这位大文豪颇有古风，喜欢用单字（“a”）胜过长单词（“ffsda”），而且用词比例正符合幂律分布：在双log坐标系下，图像大致是一条直线。这很符合直觉：为了得到任何长度大于1的单词，猴子第二次敲的按钮必须不是空格。

不要嘲笑我们的前辈，人类的语言也具有相同的性质，虽然概率最高的字是the什么的。并不是Zipf’s law限制了猴子打出十四行诗，这或许是个好消息。

连接曲别针，第一种方法

在墙上钉100个钉子，然后随意把曲别针连在上面。哪个钉子上曲别针越多，下一个曲别针挂在上面的概率就越高。

l=100
list=np.ones(l)
for i in range(100000):
    s=sum(list)
    p=[j/s for j in list]
    k=np.random.choice(l,1, p=p)
    list[k]+=1
plt.plot(sorted(list,reverse=True))
plt.xscale('log')
plt.yscale('log')
plt.show() #指数分布

可惜这只是个指数分布，与幂律分布相比，指数分布更加“平缓”，而且在双对数坐标系下也并不是一条直线。

连接曲别针，the right way

现在，我有一把曲别针。我随便拿出两个曲别针，并把它们两个所在的串连接起来。

假设我对每一个曲别针没有特别的爱好，那么，某个串选中的概率，与串中的曲别针个数正相关。这就是所谓的优先连接性。

tic=timeit.default_timer()
l=20000
list=[1]*l
while len(list)>14000:
    s=sum(list)
    p=[j/s for j in list]
    k1=np.random.choice(len(list),1, p=p)
    a1=list.pop(k1[0])
    s=sum(list)
    p=[j/s for j in list]
    k2=np.random.choice(len(list),1, p=p)
    a2=list.pop(k2[0])
    list.append(a1+a2)
toc=timeit.default_timer()
print(toc-tic)
plt.plot(sorted(list,reverse=True))
plt.xscale('log')
plt.yscale('log')
plt.show()