优先链接
优先链接 Preferential Attachment是一类过程，在这类过程中，某些量(通常是某种形式的财富或信贷)是根据一些人或事物已经拥有的量来分配的，从而使那些已经富有的人比那些不富有的人得到更多。”优先链接”是描述该过程的众多名称中最贴近其本质含义的名称。它还被称为“Yule过程”、“优势积累”、“富人越来越富” ，以及说得不那么确切的“马太效应”。它们也与吉布拉定律有关。优先链接之所以受到科学家的关注，主要是因为它能在适当的条件下产生幂律分布 Power Law Distributions。
定义
优先链接过程是一个随机瓮过程 Stochastic Urn Process，也就是说离散的财富单位(通常称为“球”)，以随机或部分随机的方式添加到一组物体或容器(通常称为“瓮”)。优先链接过程是一个瓮过程，在这个过程中，额外的球被不断地添加到系统中，并作为瓮中已有球数的递增函数分配到瓮中。尽管在最常研究的例子中，翁的数量也在不断增加，但是这不是优先链接的必要条件，有一些研究的例子伴随着翁数量不变甚至减少的现象。
优先链接过程的一个典型例子是生物有机体的某些高级分类单元中每个属的物种数量的增长。[1]每当一个新出现的物种被认为与其祖先完全不同，不属于任何一个现有属时，新属(“urns”)就被添加到分类单元中。新物种(“球”)加入的时候旧物种发生演变(即一分为二)，如果认为新物种与其亲本属于同一属(除外它们本身是新属)，那么新物种加入该属的概率将与该属已有的物种数量成正比。这个首先被Yule研究的过程，就是一个线性优先链接的过程，因为新物种的繁殖率与其已经拥有的数量成线性关系。
翁的数量增加的线性优先链接过程，会在翁中按照所谓的Yule分布产生球的分布。在最一般形式的过程中，球添加到系统中的整体速率是每个瓮中添加m个新球。每个新创建的瓮都以 k0 个球开始，然后新球被不断地添加到瓮中，其速度与瓮的数量k加常数 a > >k0成正比。利用这些定义，可以给出长时极限下具有k个球的瓮的分数P(k)[2]:
[math]\displaystyle{ P(k)={\mathrm{B}(k+a,\gamma)\over\mathrm{B}(k_0+a,\gamma-1)}, }[/math]
对于k ≥ k0(否则为0) ，其中 b (x，y)是 Euler beta 函数:
[math]\displaystyle{ \mathrm{B}(x,y)={\Gamma(x)\Gamma(y)\over\Gamma(x+y)}, }[/math]
(x)是标准伽马函数，并且
[math]\displaystyle{ \gamma=2 + {k_0 + a\over m}. }[/math]
对于较大的x和固定的y，β函数表现为B(x, y) ~ x−y，这意味着对于k的大值，我们有一个渐近的β函数
[math]\displaystyle{ P(k) \propto k^{-\gamma}. }[/math]
换句话说，优先链接过程在其尾部产生一个遵循帕累托分布 Pareto Distribution或幂定律 Power Law的“长尾”分布 Long-Tailed Distribution。这是历史上人们对优先链接感兴趣的主要原因: 经过实际的观察，物种分布和许多其他现象都遵循幂律分布，而优先链接过程是解释这种行为的主要候选机制。它还可能解释如城市规模的分布[3]，大富豪的财富[3] the number of citations received by learned publications,[4]，以及万维网网页的链接数量等问题。[5]
这里描述的一般模型包括许多作为特例的其他特定模型。例如，在上面的种属例子中，每个属以一个单一的种(k0 = 1)开始，并且获得的新种正比于它已有的种的数量(a = 0) ，因此P(k) = B(k, γ)/B(k0, γ − 1)，γ=2 + 1/m. 。类似地，科学引文的价格模型 Price Model[4] 对应于k0 = 0，a = 1 ，而广泛研究的Barabási-Albert 模型[5]对应于 k0 = m, a = 0.。
优先链接有时被称为马太效应，但两者并不完全等同。马太效应，最早由罗伯特·金·莫顿讨论[6]，是根据《圣经》中的一段马太福音命名的: 凡有的，还要加给他，叫他有余；凡没有的，连他所有的也要夺去。(马太福音25:29，新国际版)。优先链接过程并不包括夺走的部分。但是这一说法可能没有意义，因为马太效应背后的科学见解无论如何都是不一样的。定性地说，它并不是像如优先链接一样在描述一种机械的乘法效应，而是在描述一种特定的人类行为。在这种行为中，人们更有可能给归功于名人而不是归功于小透明。马太效应的经典例子是：两个不同的人同时做出了某项科学发现，其中一个人十分有名，另一个人则鲜为人知；据称，在这种情况下，人们往往更倾向于将这一发现归功于著名的科学家。因此，马太效应所要描述的现实景象与优先链接是截然不同的(虽然肯定与优先链接有关)。
历史
1925年，那时的Udny Yule是第一个对优先链接进行严谨考量的人，他用它来解释被子植物属中物种数量的幂律分布。[1]为了纪念他，这个过程有时被称为“Yule过程”。Yule能够证明这个过程产生了一个带有幂律尾巴的分布，但是他的证明的细节，按照今天的标准，是曲折和晦涩的，因为现代的随机过程理论工具当时还不存在，他被迫使用更加繁琐的证明方法。
大多数现代优先链接的处理方法都使用了主方程方法 Master Equation Method，这种方法在1955年由 Simon 首创，用于研究城市规模和其他现象的分布。[3]
普赖斯于1976年首次将优先链接应用于学术引文。[4](他把这个过程称为“优势累积” Cumulative Advantage过程。)他也是第一个将这一过程应用于网络发展的人，他创造了现在所谓的无标度网络 Scale-Free Network。正是在网络增长的背景下，这一过程在今天得到了最频繁的研究。普莱斯还将优先链接作为许多其他现象中幂定律的可能解释，包括洛特卡的科学生产力定律和布拉德福德的期刊使用定律。
1999年，Barabási 和 Albert 提出了优先链接在万维网发展中的应用。[5]他们也杜撰了该过程被广为知晓的名字——“优先链接”，并且表明这个过程也可以应用于其他网络的增长。对增长的网络来说，优先链接的精确作用形式可以用极大似然估计来估计。[7]
参见
- 关联矩阵
- BA模型
- 玻色-爱因斯坦凝聚：一种网络理论方法
- 资本积累
- 中餐厅过程
- 复杂网络
- 双重危险（营销）
- 以链接为中心的优先链接
- 马太效应（社会学）
- Pitman-Yor过程
- 幂定律
- 价格模型
- 权益证明
- 西蒙模型
- 随机过程
- 财富集聚
- Yule-Simon 分布
- 书目图
参考文献
- ↑ 1.0 1.1 Yule, G. U. (1925). "A Mathematical Theory of Evolution, based on the Conclusions of Dr. J. C. Willis, F.R.S". Philosophical Transactions of the Royal Society B. 213 (402–410): 21–87. doi:10.1098/rstb.1925.0002.
- ↑ Newman, M. E. J. (2005). "Power laws, Pareto distributions and Zipf's law". Contemporary Physics. 46 (5): 323–351. arXiv:cond-mat/0412004. Bibcode:2005ConPh..46..323N. doi:10.1080/00107510500052444.
- ↑ 3.0 3.1 3.2 Simon, H. A. (1955). "On a class of skew distribution functions". Biometrika. 42 (3–4): 425–440. doi:10.1093/biomet/42.3-4.425.
- ↑ 4.0 4.1 4.2 Price, D. J. de S. (1976). "A general theory of bibliometric and other cumulative advantage processes" (PDF). J. Amer. Soc. Inform. Sci. 27 (5): 292–306. doi:10.1002/asi.4630270505.
- ↑ 5.0 5.1 5.2 Barabási, A.-L.; R. Albert (1999). "Emergence of scaling in random networks". Science. 286 (5439): 509–512. arXiv:cond-mat/9910332. Bibcode:1999Sci...286..509B. doi:10.1126/science.286.5439.509. PMID 10521342.
- ↑ Merton, Robert K. (1968). "The Matthew effect in science". Science. 159 (3810): 56–63. Bibcode:1968Sci...159...56M. doi:10.1126/science.159.3810.56. PMID 17737466.
- ↑ Pham, Thong; Sheridan, Paul; Shimodaira, Hidetoshi (September 17, 2015). "PAFit: A Statistical Method for Measuring Preferential Attachment in Temporal Complex Networks". PLoS ONE. 10 (9): e0137796. Bibcode:2015PLoSO..1037796P. doi:10.1371/journal.pone.0137796. PMC 4574777. PMID 26378457.
类别: 随机过程
编者推荐
集智文章
集智文章|粗看长尾，细辨幂律：跨世纪的无标度网络研究纷争史
维弗雷多·帕累托（Vilfredo Pareto ，1848—1923），福利经济学先驱；乔治·金斯利·齐普夫（George Kingsley Zipf，1902-1950），计量语言学先驱；德里克·普莱斯（Derek John de Solla Price，1922-1983），科学计量学之父；赫伯特·亚历山大·西蒙（Herbert Alexander Simon，1916-2001），人工智能先驱；波努瓦·曼德布罗特（Benoit B. Mandelbrot，1924-2010），分形之父；艾伯特-拉斯洛·巴拉巴西（Albert-László Barabási，1967-），当今网络科学研究代表人物、无标度网络概念提出者。
如果能够把这些横跨三个世纪、来自不同领域的科学先驱组织在一起召开主题论坛的话，他们讨论甚至争论的主题也许只有一个：幂律（Power Law）分布。本文通过围绕网络科学中的核心概念——无标度网络、幂律分布以及偏好链接机制的“多次重复发现”和“多轮争议”的故事，与读者分享网络科学研究的曲折而又动人的历程。
从网络科学的眼光看，这些研究和争议本身就串成了一个网络，本文希望能够让更多的读者体验到这一网络的精彩纷呈。需要事先声明的是，关于无标度网络研究的文献众多，从经验验证到建模、从特征分析到控制等等。即使是关于其定义本身的研究也有包括我国学者史定华教授在内的一些学者的工作。本文远非无标度网络研究历史的完整记录，而只是围绕着本文的主题，选取其中我们认为有关联的少数节点加以阐述。
解读幂律分布与无标度网络 | 长文综述
本文介绍了幂律分布的形式、特点以及无标度网络的形式和特点，特别是无标度网络在于抵御攻击和传染病传播上的特异性。列举了一些经典的幂律分布随机变量生成机制，最后简介了对数线性回归和极大似然对于幂律指数的估计方式以及KS检验在幂律分布检验上的应用。
集智视频
无标度网络与幂律分布
本课程中，将解释复杂性研究领域的两次著名争论之间千丝万缕的联系。一是1955年至1961年，人工智能之父西蒙与分形之父曼德布罗特关于幂律分布起源的争论；二是2018年，克劳塞特和巴拉巴西关于真实世界是否广泛存在无标度网络的争论。
无标度性质在网络科学的发展过程中发挥了非常重要的作用，主要有以下两点原因：
包含万维网和细胞网格在内的许多具有科学意义和实际意义的网络都是无标度的。这种普适性使得无标度性质成为许多学科都无法回避的问题。 一旦有枢纽节点存在，枢纽节点就会从根本上改变系统的行为。超小性就是枢纽节点对网络性质产生影响的例子之一。 要理解真实网络的性质，只需要记住：在无标度网络中，少数高度连接的枢纽节点和大量度很小的节点并存。这些枢纽节点的存在对于系统行为具有重要影响。本节所讨论的解析和实证结果，是后续课程关于网络建模的基础。实际上，无论研究网络的哪种性质，例如社区结构和传播过程，都必须在掌握了网络度分布的情况下进行。
复杂系统中的幂律分布
本课程结合实际数据和丰富的学术文献，从各方面向大家展示幂律分布——复杂系统入门必修课，其特征和意义，以及如何应用，为大家打造了体系完整的幂律分布学习框架！
2018年国家统计局公布的数据显示，全国居民人均可支配收入在2017年是2.6万元，如果收入满足正态分布的话，收入超过6万的人会很少。但实际上，早在2016年，就已经有20%的居民可支配收入超过了5.9万！实际上，人们的收入服从幂律分布，而不是正态分布。这意味着用平均去代表整体的水平，是有严重偏差的。
除此之外，有很多实际问题都与幂律分布相关。比如，为什么在收入、财富统计中，我们不能用均值代表总体；为什么古老的计算机病毒不能被根除；为什么你的好友比你更受欢迎；为什么大规模股灾隔三差五就会出现；为什么保险行业比我们想象的更加脆弱；为什么阿里巴巴可达千亿市值、亚马逊可达万亿市值等，这些问题都可以用幂律分布的相关知识进行解释。
本课程结合实际数据和丰富的学术文献，从各方面向大家展示幂律分布——复杂系统入门必修课，其特征和意义，以及如何应用，为大家打造了体系完整的幂律分布学习框架！
本中文词条由Ryan参与编译，Fernando审校，糖糖编辑，如有问题，欢迎在讨论页面留言。
本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。