前言

看一些图论文的时候可能经常会遇到这个词
某个结点的degree服从power law。
度数（邻居结点数/边数）服从幂律。

第一次看到的时候蒙蔽了一下，
但是这些作者似乎都把这句话当成一个初级结论，不需要证明了。
搞得我很奇怪，难道这是哪个教科书上的定理？
作者们上过同一门课因此觉得大家都知道就不解释了。
但是我没上过课啊！！！

最后还本溯源让我找到了这篇1999年的论文。

A. L. Barabasi and R. Albert. 1999. Emergence of scaling in random networks. Science 286, 5439 (October 1999), 509–512. http://view.ncbi.nlm.nih.gov/pubmed/10521342

论文内容

现实数据集(real dataset)中存在一个普适性规律。
即任意结点与k个其他结点连边的概率服从指数幂分布(Power Law Distribution)。
数学化表示即

结点u有k条连边的概率$P(k)$
$P(k)\sim k^{-\gamma },\gamma >0,k>0$

其中$\gamma$是一个与u本身相关的参数。

论文中举例，
演员数据集中${\gamma }_{actor}=2.3\pm 0.1$，
www数据集中${\gamma }_{www}=2.1\pm 0.1$
论文引用关系里${\gamma }_{cite}=3$

显然gamma越大，每个结点的连边倾向于较少。

而上述公式显然与整个网络的规模（总结点数）无关。
无论你有100个结点还是一万亿个结点，每个结点拥有k条连边的概率都服从同一个分布。
因此这个公式向我们揭示了现实世界中存在的 scale-invariance 规律。

但是我有一个问题。
显然P(k=1)=1，那么我们将k=1,2,…,+∞下的P(k)加起来，概率值是大于1的。
和大于1是可以接受的吗。。。？
针对这个疑问，论文里有一句following a power law for large k with an exponent，
也就是说仅当k足够large时，才服从这一规律。k=1这种很小的时候不算？
那应该遵循怎样的分布去构造只有1个连边的结点呢？？？
希望看到本文的有缘人能一起讨论这个问题。

这个规律可以指导我们合成假的人工数据集(fake dataset)。
我们在人工合成数据的时候，也应该保证类似的指数幂分布。

例如给定n个很相似的结点，可以假定他们的$\gamma$是一致的。
那么就可以按照指数幂产生概率p值。
最终决定这n个点有几条连边。
（或者说他们的degree分别为多少）

真实数据集存在两个点，与常见假设不同。
其一，增长性(growth)。
一般理论上的数据集的结点数N是不变的，但是现实中网络一般是随时间扩大的。
其二，偏好连接（preferential attachment)。
一般认为随机数据集中的连边是均匀产生，均匀分布的。但事实上，现实中的点与点之间往往采取偏好连接。

举例，演员数据集中，老的well-known演员显然更容易被连接。所以我们插入新结点的时候，新结点更倾向于跟老结点连。即存在马太效应，度数越高的结点反而更容易获得连边。

1.以一个较小的结点数m0作为初始化的图。initial graph里的结点之间怎么连边，作者没有讲。我自己实践的时候让这m0个结点两两互连了，这样最无脑吧，而且邻接矩阵比较好写。eye() - ones()就行了。
2.每一步向图中1个新结点，新结点与已存在的结点之间随机增加m(m<m0)条边。
3.重复上述过程，直到总结点数达到预设的n个。

这样一来，最早加入的结点有较大概率获得更多的邻居。
而最后面加入的结点的连边显然就比较少了。

问题来了！！！

如果你的m0=10，m=9。
显然每个加入的结点怎么样都会有至少9个连边。
这样构造的假数据集，就不存在邻居结点小于9的结点了。
这样的数据集足够real吗？？？
我个人持有很大的怀疑！！！

所以说我们的m需要取的比较大，但是不能取太大？？？

为了抵消这种奇葩的结果，我试着设置m0=2，m=2。
这样产出的数据集，不存在只有一个连边的结点，最少有2个连边。
虽然还是不那么real，好歹稍微可接受一点了。

不知道是不是我没明白这篇论文的思想才导致写代码有问题。
因为论文里的m看起来是个固定的超参数。

如果你要说m本身是个服从幂次分布的随机数，问题似乎就能解决了。但是论文里不像这个意思啊。

t次之后，m0+t个结点。一共有mt条边。这不是说明m是固定值吗？
还有，只有mt条边，似乎又在暗示那个初始图里，m0个结点之间是没有互相连接的。
可是这样的话，第一个新加入的结点的概率p要从哪里来呢？这种情况下$\Pi (k_i)$的计算式里，分子分母全部是0啊。

20年前的论文了，总不能把作者抓出来拷问一顿吧。

恳请后来人指教。

最后

以上就是害羞中心为你收集整理的图数据集的幂次规律前言论文内容的全部内容，希望文章能够帮你解决图数据集的幂次规律前言论文内容所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。