最先发现无标度网络的人竟然是他!?-集智俱乐部

从无标度网路研究历史看想法传播

导语

网络科学的关键节点是1999年的Barabási等人的无标度网络模型和1998年邓肯瓦茨等人的小世界网络模型。但网络科学的起点真的在这里吗?不,网络科学的思想脉络其实非常久远。

本文整理自汪小帆教授在计算传播学年会上的演讲《从无标度网络研究历史看想法传播》(演讲视频回放https://campus.swarma.org/gcou=10587)

科学上有一个普遍的现象,是同一个科学发现,它的不同形式在不同时间和地点被不同的人重新发现,这样的例子屡见不鲜。

1.网络科学二十年,

何处是起点?

点燃网络科学的两篇文章是1998和1999年的两篇经典论文。

最先发现无标度网络的人竟然是他!?-集智俱乐部

1998和1999年的两篇经典论文

这两篇文章每篇都有超过三万次的引用,我们从文章被引变化,看到了它们是如何点燃身后的网络科学研究轨迹。本文将以无标度网络为例,试图追溯其思想源头。

什么是无标度网络,简单说就是说一个网络上节点的度(节点所在连边的数量)分布服从幂指数为2和3之间的幂律分布该网络中大部分节点的度值较小,少部分节点的度值较大。

广义来说,只要这个网络不具有特征尺度,也是是说它的平均度值不代表这个网络的典型度值,我们就称它是无标度网络。从物理学角度看,如果一个网络中节点的度值有个位数的,有十位数的,也有百位数和千位数的,有有不同数量级的度值,我们可以粗略认为它是无标度网络。而在数学上,则把幂函数的标度不变性作为判断标准。

最先发现无标度网络的人竟然是他!?-集智俱乐部

无标度网络

1999年Barabási小组发了两篇文章,第一篇文章将万维网是无标度网络,其入度分布、初读分布都服从幂律分布。而第二篇文章,将不仅万维网、还有其他几种网络度分布也符合幂律分布,进而提出了无标度网络模型,所谓BA模型。

最先发现无标度网络的人竟然是他!?-集智俱乐部

提出无标度网络BA模型的 Barabási(中)研究组,Albert(左),Jeong(右)

BA模型基于两个假设,1.网络不断增长,2.增长过程服从优先连接机制,即新加入的节点倾向于连接那些已有连边较多的节点。这是一个非常精彩的假设,但在原始论文中,没有给出与这一思想有关的参考文献。

没有相关参考文献的原因可能有两种,一种是他们之前没有人发现网络的这一特征,第二种是确实有前人的基础研究,但作者没有看到。

2.幂律分布和优先连接,

Price模型早已看透

实际上,我们通过文献检索,还是可以看到前人留下的蛛丝马迹。第一个浮出水面的,是这位Price(Derek J.de Solla Price)。

最先发现无标度网络的人竟然是他!?-集智俱乐部

Price早在1965年,就发表了一篇《Power law in citation Networks》。该研究结论中不管是出度还是入度,其实都是服从幂律分布的,甚至连幂指数都给出来了。

最先发现无标度网络的人竟然是他!?-集智俱乐部

Derek John de Solla Price(1922-1983),英国物理学家,科学计量学之父,最早在科学引文网络中发现了无标度网络

所以1999年的“万维网是幂律分布”大家认为是伟大发现,但其实60年代就有过很明确的对于网络度幂律分布的研究,只是当时没有引起太大关注。

到1976年,Price更是写了一篇文章,简直就是1999年Barabási那篇文章的70年代翻版。他提出了一个累积优势的分布,该分布基于“成功的人更成功”,其实就是优先连接的通俗说法。

Price不仅揭示了网络节点的度存在幂律分布,甚至给出了幂律分布的增长有有优先连接机制,其思想与今天的BA网络很接近。Price模型就是BA模型的无向形式,它甚至更加一般化。在Mark Newman的经典教材Networks中,用很长的篇幅阐述了Price的贡献。

最先发现无标度网络的人竟然是他!?-集智俱乐部

3.Simon,

人工智能先驱对网络科学的贡献

我们自然会继续追问,Price的思想是从哪里来的?

在Price提出连接机制的文章中,提到了“语言中一个单词出现的次数会越来越多,有的会越来越少,在统计中这样的构成被称为skew or hyperbolic distribution function(偏斜或双曲分布函数),而这一函数是由Simon最先刻画出的”。显然,Price的思想受到了Simon的启发。

最先发现无标度网络的人竟然是他!?-集智俱乐部

Herbert Simon(1916-2001),计算机科学家,多个研究领域的开创者

Simon是著名的计算机科学家,人工智能的先驱。他的交叉学科可能无人能比,获得了政治学的博士学位,获得美国心理学界的最高奖,获得了计算机科学的图灵奖,获得了经济学的诺贝尔奖…

最先发现无标度网络的人竟然是他!?-集智俱乐部

Simon在1955年写的分布特征的文章

Simon在1955年的时候,就写过于一种概率密度分布的文章。他以写书为例,假设你正在写一本书,并且已经写了k个单词,那么第k+1个单词是一个新单词的概率为α,第k+1个单词是旧单词的概率是1-α。

由此就可以得到:一个已有单词被选中的概率与该单词已经出现的次数成正比。这就是典型的优先连接。

最先发现无标度网络的人竟然是他!?-集智俱乐部

Simon描述的Yule-Simon分布

从这一角度看,Price模型是Simon模型的网络形式,一篇已有文章被引用的概率与该文章已被引用的次数成正比。而BA模型是Price模型的无向化,一个已有节点被选中的概率与该节点的度值成正比。

我们继续追问,Simon继承了谁的想法?

4.Yule,优先连接机制的源头

Simon在文章把他介绍的分布命名为Yule-distribution,认为这应该归功于统计学家Yule。

详情请见维基百科的Yule-Simon distribution词条:https://en.wikipedia.org/wiki/Yule–Simon_distribution

最先发现无标度网络的人竟然是他!?-集智俱乐部

Yule (1922)画出的物种分布曲线

Yule 在1922年发现,在生物分类中,少量的属包含大量的物种,而大多数的属只有少量的物种,物种分布是服从幂律分布

而在1925年,Yule 对为什么物种种类分布服从幂律分布从数学角度做了解释。

最先发现无标度网络的人竟然是他!?-集智俱乐部

Udny Yule(1871-1951),英国统计学家

物种突变有两种类型,一种是小的变异,在同一个属内产生新物种,速度为s。另一种大的变异,直接产生一个新的属,速度为g。由这两种产生新物种,速度不同,但速度又相对稳定。而物种分布曲线的幂指数,正是由这两个速度的比值s/g决定的。

在论文中虽然没有针对复杂网络,但Yule已经画出漂亮的双对数曲线,清晰地看到幂律分布的特征,并且从物种诞生的概率和速度的角度,对幂律分布的成因做出了解释。

最先发现无标度网络的人竟然是他!?-集智俱乐部

无标度网络研究的随机框架的历史脉络(另一条优化框架的脉络,请看演讲回放)

这一路下来,我们就找出了幂律分布产生的随机框架——从Yule到Simon再到Price的脉络。幂律分布的随机框架一直可以追溯到1924年,一百年前的科学家不仅发现了幂律分布,而且甚至给出了产生幂律分布的优先连接机制。

在科学传播中,我们往往认为第一个发现的最重要,但事实上,很多时候你根本不知道第一个发现的是谁。往往是最后一个发现的,反而是最重要的。所谓最后一个发现,其实是“直到它为止,这个现象才推广传播开、才被公认”。

科学思想传播的这一特点,在网络科学领域十分明显。

编辑:孟婕

推荐阅读

社交网络中的幂律分布:为什么有的人微信好友5000而你只有500?

解读幂律与无标度网络 | 网络科学入门

理论危机 | 无标度网络遭到史上最严重质疑

Love is All You Need | 无标度网络理论之父Barabási回应史上最严重质疑

加入集智,一起复杂

幂律与规模读书会

关于幂律分布复杂网络集智俱乐部将组织4次读书会,进行线下分享与讨论,点击查看了解详情:发现复杂世界的简单规则:幂律与规模读书会

最先发现无标度网络的人竟然是他!?-集智俱乐部

《规模》作者 West 集智开讲

复杂系统中一套普适的幂律关系,就是规模法则。作为圣塔菲研究所前任所长,West专门写了一本《规模》(Scale)来解读规模现象,如今更是来到北京开展专题讲座,不要错过!

最先发现无标度网络的人竟然是他!?-集智俱乐部

复杂系统中的幂律分布

系统学习

幂律的力量,我们其实一无所知。

最先发现无标度网络的人竟然是他!?-集智俱乐部


最先发现无标度网络的人竟然是他!?-集智俱乐部

集智俱乐部QQ群|877391004

商务合作及投稿转载|swarma@swarma.org

搜索公众号:集智俱乐部

加入“没有围墙的研究所”

最先发现无标度网络的人竟然是他!?-集智俱乐部

让苹果砸得更猛烈些吧!

最先发现无标度网络的人竟然是他!?-集智俱乐部点击|阅读原文|看演讲录像

原文始发于微信公众号( 集智俱乐部 ):集智