7,129
个编辑
更改
跳到导航
跳到搜索
→广义无标度模型
{{#seo:
|keywords =幂律分布,无标度网络,集智
|description =无标度性,依附模型,规模不变形
}}
'''无标度网络 scale-free network'''是一种[[度分布]]（即对复杂网络中节点度数的总体描述）服从或者接近[[幂律分布]]的[[复杂网络]]。无标度网络中某节点与另外 <math> k</math> 个节点相连接（度数为 <math>k</math> ）的概率是：
<center><div style="width:500px;height:30px">
<div style="float:left;width:400px"><math>P(k) \sim \ k^\boldsymbol{-\gamma}</math></div>
<div style="float:left;"><math>(1)</math></div></br>
</div></center>
其中， <math>{\gamma} </math> 是一个通常位于2和3之间的参数，但偶尔也会在这个区间之外。<ref>Onnela, J. -P., Saramaki, J., Hyvonen, J., Lazer, G., Kaski, D., Kertesz, K., Barabasi, J., A. -L. (2007) [https://pattern.swarma.org/paper?id=efb73d0a-7820-11ea-991e-0242ac1a0005 "Structure and tie strengths in mobile communication networks"].Proceedings of the National Academy of Sciences, doi:10.1073/pnas.0610245104. PMC 1863470. PMID 17456605..104.18:(7332--7336)</ref><ref>Krzysztof Choromański,Michał Matuszak,Jacek Miȩkisz (2013) [https://pattern.swarma.org/paper?id=086fb46c-6d95-11ea-bc89-0242ac1a0005 Scale-Free Graph with Preferential Attachment and Evolving Internal Vertex Structure].journal of statistical physics.151.6:(1175-1183)</ref>
许多网络似乎都体现出无标度的特性，然而统计分析却表明许多网络并不符合无标度特性。<ref name="Aaron Clauset">Aaron Clauset, Cosma Rohilla Shalizi, M E J Newman () [https://pattern.swarma.org/paper?id=88199410-6da6-11ea-b59a-0242ac1a0005 Power-Law Distributions in Empirical Data].51.4:(661-703)</ref><ref>Broido (2019) [https://pattern.swarma.org/paper?id=7e21863a-7822-11ea-ba18-0242ac1a0005 "Scale-free networks are rare"].Nature Communications.10.1:(1017)</ref>
[[偏好依附 preferential attachment]]和[https://en.wikipedia.org/wiki/Fitness_model_(network_theory) 适应度模型 fitness model]是对现实中的网络如何产生幂律度分布的可能解释。
==历史==
在对科学引文网的研究中，[[普赖斯 Derek de Solla Price]]在1965年发现：论文的链接数，即该论文被引用的次数，服从[https://en.wikipedia.org/wiki/Heavy-tailed_distribution 厚尾]的[https://en.wikipedia.org/wiki/Pareto_distribution 帕累托分布 Pareto distribution]或者[[幂律分布]]，由此得出引文网络是无标度的。然而他当时并未使用“无标度网络”这个术语。这个术语直到几十年之后才出现。在1976年的论文中，普赖斯还提出了一种解释引文网络产生[[幂律分布]]的机制，他称之为“累积优势 cumulative advantage”，也就是现今更被熟知的“[[偏好依附 preferential attachment]]”。
近期对无标度网络的关注始于1999年圣母大学的[https://en.wikipedia.org/wiki/Albert-L%C3%A1szl%C3%B3_Barab%C3%A1si 艾伯特-拉斯洛·巴拉巴西 Albert-László Barabási ]及其同事着手对部分万维网的拓扑结构进行绘制。<ref name="Barabási1999">Barabási, Réka. (1999) [https://pattern.swarma.org/paper?id=ced492e8-7822-11ea-8a27-0242ac1a0005 "Emergence of scaling in random networks"].Science.286.5439:(509--512)</ref>他们发现有些他们称之“'''枢纽 hubs'''”的节点比其他节点具有更多的链接数，同时网络任意节点的链接数服从[[幂律分布]]。在发现其他的网络，如部分社会网络和生物网络也具有厚尾的度分布之后，巴拉巴西及其同事创造了“无标度网络 Scale-free network”一词来描述这类度分布呈幂律的网络。Amaral等人指出，可以根据大k值的度分布的衰减，将大部分现实世界的网络归为两个大类。
巴拉巴西和艾伯特提出了一种他们称之为[[偏好依附 preferential attachment]]的生成机制，用来解释[[幂律分布]]，这基本上和普赖斯提出的机制相同。这种机制的解析解（也与普莱斯的相似）由Dorogovtsev，Mendes和Samukhin<>Dorogovtsev, S., Mendes, J., Samukhin, A. (2000) [https://pattern.swarma.org/paper?id=81070e4a-7824-11ea-8fd8-0242ac1a0005 "Structure of Growing Networks with Preferential Linking"].Physical Review Letters.85.21:(4633--4636)</ref>于2000年提出，Krapivsky，Redner和Leyvraz 等人也同时独立提出。后来由数学家[[贝拉·波洛巴斯 BélaBollobás]]严格证明。<ref>Bollobás, B., Riordan, O., Spencer, J., G. (2001) [https://pattern.swarma.org/paper?id=f16b5632-7824-11ea-9332-0242ac1a0005 "The degree sequence of a scale-free random graph process"].Random Structures and Algorithms.18.3:(279--290)</ref>
然而这种机制所生成的网络只是无标度网络这个大类中的特殊子集，许多其他机制自此也陆续被发现。<ref>Dorogovtsev, S. N., Mendes, J. F. F. (2002) [https://pattern.swarma.org/paper?id=4b0fcde6-7828-11ea-93d6-0242ac1a0005 "Evolution of networks"].Advances in Physics.51,.(1079--1187)</ref>
无标度网络的历史还存有一部分争议。在实证层面上，许多网络的无标度性被质疑。如Faloutsos三兄弟认为互联网是基于网络层错觉，实则是体现为高度节点的[https://en.wikipedia.org/wiki/Autonomous_system_(Internet) ASes]数据链结构。<ref>Willinger (2009) [https://pattern.swarma.org/paper?id=c60be3ae-7828-11ea-ab3c-0242ac1a0005 "Mathematics and the Internet: A Source of Enormous Confusion and Great Potential" (PDF). Notices of the AMS].American Mathematical Society.56.5:(586--599)</ref>
在理论层面上，研究者提出了对无标度的抽象定义的改良。例如李等人（2005）近日提供了更加准确的“无标度指标”。简而言之，定义 <math>G</math> 是具有连边集合E的图，顶点 <math>v</math> 的度（即与<math>v</math>邻接的边的数量）记为<math>deg\left ( v \right )</math>。定义：
<center><div style="width:500px;height:30px">
<div style="float:left;width:400px"><math>s(G) = \sum_{(u,v) \in E} \deg(u) \cdot \deg(v)</math></div>
<div style="float:left;"><math>(2)</math></div></br>
</div></center>
<math>s(G)</math>在高度节点与其他高度节点邻接时最大。定义：
<center><div style="width:500px;height:30px">
<div style="float:left;width:400px"><math>S(G) = \frac{s(G)}{s_\max}</math></div>
<div style="float:left;"><math>(3)</math></div></br>
</div></center>
其中，<math>{s}_{max}</math> 是所有与 <math>G</math> 的度分布相同的图的集合中图 <math>H</math> 的 <math>s(H)</math> 的最大值。 <math>S(G)</math> 是一个值域在0和1之间的指标，具有较小 <math>S(G)</math> 的图 <math>G</math> 是“丰标度”的，一个具有接近1的 <math>S(G)</math> 的图 <math>G</math> 是“无标度”的。这个定义体现了“无标度”所隐含的[[ 自相似性]]的概念。
==特征==
[[File:Scale-free_network_sample.png| 330px | thumb |right |随机网络（a）和无标度网络（b) 深色标记了无标度网络中的枢纽]]
[[File:Complex_network_degree_distribution_of_random_and_scale-free.png| 330px | thumb |right |随机和无标度复杂网络的度分布]]
无标度网络的特性是普遍存在度远高于平均值的节点。度最高的节点通常称为枢纽 hub，被认为在网络中起到特殊作用，尽管这还要看具体在网络的哪个区域。
无标度性与网络应对失败的鲁棒性有很大关系。主要的枢纽节点通常连接着小的枢纽节点。这些小的枢纽节点再伴随着度更小的节点，以此类推。这种层级关系使得网络能够[https://en.wikipedia.org/wiki/Fault-tolerance 容错 fault tolerant]行。如果错误随机发生，并且大量节点都具有较小的度，那么枢纽节点几乎不会受到影响。即便枢纽节点出现了错误，因为还有其他枢纽节点，网络通常不会失去原来的[https://en.wikipedia.org/wiki/Connectedness 连通性 connectedness]。然而，如果定向选择一些主要的枢纽节点并把它们从网络中去除，网络则会变为许多相对离散的图。因此，枢纽节点既是无标度网络的优势又是劣势。Cohen<ref>Cohen, K., Avraham, D., Havlin, S. (2000) [https://pattern.swarma.org/paper?id=ce02a3ee-7829-11ea-be52-0242ac1a0005 "Resilience of the Internet to Random Breakdowns"].Physical Review Letters.85.21:(4626--4628)</ref><ref>Cohen, K., Avraham, D., Havlin, S. (2001) [https://pattern.swarma.org/paper?id=523f6e44-782a-11ea-abd8-0242ac1a0005 ben-, "Breakdown of the Internet under Intentional Attack"].Physical Review Letters.86.16:(3682--3685)</ref>和Callaway<ref>Callaway, M. E. J., Watts, S. H., D. J. (2000) [https://pattern.swarma.org/paper?id=6ca146bc-782b-11ea-8cca-0242ac1a0005 "Network Robustness and Fragility: Percolation on Random Graphs"].Physical Review Letters.85.25:(5468--5471)</ref>等人曾用[[渗流理论 percolation theory]]分析过这些特性。
Cohen<ref>Cohen, K., Avraham, D., Havlin, S. (2000) [https://pattern.swarma.org/paper?id=ce02a3ee-7829-11ea-be52-0242ac1a0005 "Resilience of the Internet to Random Breakdowns"].Physical Review Letters.85.21:(4626--4628)</ref>证明对于大范围的无标度网络临界渗流阈值 critical percolation threshold， p_{c}=0.这表明从网络中随机删去任意数量的节点都不会破坏网络。这与 p_{c} =1/<math>\bar{k}</math>的Erdős–Rényi图形成了对比，其中 <math>\bar{k}</math> 是图的平均度。
无标度网络的另一个重要特性是随节点度数升高而降低的[[聚集系数 clustering coefficient]]分布。这个分布也服从[[幂律分布]]。这表明度数低的节点从属于致密的子图，这些子图再通过枢纽节点互相连接。试想一个社交网络，它的节点是人，而链接是熟人关系。很容易得出人们倾向于形成社群，也就是互相熟识的团体（可以将它理解为一个[https://en.wikipedia.org/wiki/Complete_graph 全连接图 complete graph ]）。另外这个小社群的人们也会有一些社群外的熟人关系。然而有些人与许多社群相连（如贵族、政治家）。这些人可以被认作是导致[[小世界现象 small-world phenomenon]]的缘由。
目前无标度网络的更具体的特性会根据他们不同的生成机制而改变。例如，由“偏好依附“生成的网络普遍将度较高的顶点放在网络的中央，将他们互相连接形成一个核心，由度逐渐降低的节点构成核心之间的区域以及外围。即便随机删除较大部分的顶点对网络整体的联通都不会有太大影响，这表明这种拓扑结构有利于提升安全性，尽管一些定向攻击会很快破坏其连通性。其他的一些将度较高的顶点放在外围的无标度网络并没有这样的性质。也就是说无标度网络的聚集系数会随着拓扑构造的改变而产生明显变化。
最后一个特性是关于网络中顶点之间的平均距离。对于大多数不规则网络，如[[小世界网络]]，这个距离相较于高度规则的[https://en.wikipedia.org/wiki/Lattice_graph 网格图]是非常小的。Cohen和Havlin证明了，2 < <math>{\gamma} </math> < 3的无关联幂律图会有非常小的半径<math>d\sim ln ln N</math>其中<math>N</math>是网络中节点的数量。<ref>Cohen, Shlomo (2003) [https://pattern.swarma.org/paper?id=3ecc6f3e-782e-11ea-8fc5-0242ac1a0005 "Scale-Free Networks Are Ultrasmall"].Physical Review Letters.90.5:</ref>
在实践中，一个生长中的无标度网络的半径几乎可以被认作是一个定值。
[[随机图]]的特性在图变形的过程中可能会变化也可能不变。正如Mashaghi A.等人所展示的，在一个将随机图转变为其双边图（或者线图）的过程中会产生一系列度分布近似，却提升了度相关性并且显著提升了聚集系数的图。<ref name="Ramezanpour">Ramezanpour, A., Karimipour, V., Mashaghi, A. (2003) [https://pattern.swarma.org/paper?id=bf724078-782e-11ea-890b-0242ac1a0005 "Generating correlated networks from uncorrelated ones"].Phys.67.4:</ref>
==示例==
[[File:Snapshot_of_weighted_stochastic_lattice.jpg|500px|缩略图|右|加权平面随机晶格 WPSL-weighted planar stochastic lattice]]
尽管许多真实世界的网络被认为是无标度的，然而其证明却往往因为愈发严格的数据分析技术而显得不够充分。<ref name="Aaron Clauset"></ref>由此，许多网络的无标度性还在科学社群中被讨论着。一些声称是无标度的网络包括：
• 社交网络包括合作网络。两个被广泛研究的示例是演员合演电影的合作网络和数学家合著论文的合作网络。
• 电脑网络包括互联网和万维网的网图。
• 一些金融网络，如银行间支付网络。<ref>De Masi (2006) [https://pattern.swarma.org/paper?id=223e74a0-7830-11ea-bd14-0242ac1a0005 "Fitness model for the Italian interbank money market"].Physical.74.6:</ref><ref>Soramäki (2007) [https://pattern.swarma.org/paper?id=969d3ce6-7830-11ea-8abd-0242ac1a0005 "The topology of interbank payment flows"].Physica A: Statistical Mechanics and Its Applications.379.1:(317--333)</ref>
• [https://en.wikipedia.org/wiki/Protein-protein_interaction 蛋白质-蛋白质相互作用 Protein-protein interaction]网络。
• [https://en.wikipedia.org/wiki/Semantic_network 语义网络 Semantic networks]。<ref>Steyvers, Tenenbaum (2005) [https://pattern.swarma.org/paper?id=af19837e-7835-11ea-a041-0242ac1a0005 "The Large-Scale Structure of Semantic Networks: Statistical Analyses and a Model of Semantic Growth"].Cognitive Science.29, 10.1:(41--78)</ref>
• 航空网络 Airline networks。
在高温超导体中也发现了无标度的拓扑结构。高温超导体<ref>Fratini (2010) [https://pattern.swarma.org/paper?id=f9f5e950-7835-11ea-840c-0242ac1a0005 "Scale-free structural organization of oxygen interstitials in La2CuO4+y"].Nature.466.7308:(841--844)</ref>
——其中电子服从量子物理，能够完美同步，零电阻地流动——似乎与看似随机的氧原子和晶格畸变的分形排列有关。<ref>Poccia, Aeppli (2012) [https://pattern.swarma.org/paper?id=383a505c-7836-11ea-b4f2-0242ac1a0005 "Optimum inhomogeneity of local lattice distortions in La2CuO4+y"].PNAS.109.39:(15685--15690)</ref>
近日发现，一种填充空间的元胞结构，[https://en.wikipedia.org/wiki/Weighted_planar_stochastic_lattice_(WPSL) 加权平面随机晶格]的配位数分布服从[[幂律分布]]。这暗示着晶格有一小部分区块，与它们公用边界的邻居的数量惊人地多。其构造由一个类似于将单位面积的正方形随机分割为四个区块发生器引发。于是这个发生器不断地被可用区块中的一个吸引，这个区块是从对应区域中择优选取的。这个动作将正方形划分为更小的互斥矩形块。通过用区块中心处的节点替换每个区块，再把区块间的公共边界替换为连接对应顶点的边，从而获得的WPSL（DWPSL）的对偶形成了一个度分布呈[[幂律分布]]的网络。<ref>Hassan, M. K., Hassan, M. Z., Pavel, N. I. (2010) [https://pattern.swarma.org/paper?id=fe62fb2c-783f-11ea-ac8c-0242ac1a0005 "Scale-free network topology and multifractality in a weighted planar stochastic lattice"].New Journal of Physics.12.9:</ref><ref>Hassan, M. K., Hassan, M. Z., Pavel, N. I. (2010) [https://pattern.swarma.org/paper?id=5f04729e-7840-11ea-9600-0242ac1a0005 "Scale-free coordination number disorder and multifractal size disorder in weighted planar stochastic lattice"].J. Phys.: Conf. Ser.297.(01)</ref>
它按照[https://en.wikipedia.org/wiki/Mediation-driven_attachment_model 中介驱动的依附模型 mediation-driven attachment model]规则生成，这看上去也体现着偏好依附的规则。
==构建模型==
无标度网络的出现不仅仅是时运使然。Erdős和Rényi (1960)研究了一种在每一个步骤中均匀地随机选择两个节点然后在他们之间加入链接的图生成模型。这些[[随机图]]中的特性与无标度网络很不一样，因此需要一种生成过程的模型。
最被熟知的无标度网络子集的生成模型是Barabási和Albert(1999)的[https://en.wikipedia.org/wiki/Rich_get_richer 富者更富 rich get richer]模型生成，它让每个网页根据一个非均匀的概率分布与既存网页建立连接，这个概率分布与当前网页的入度数成比例。这个模型最初由普赖斯在1965 年发明，并命名为累积优势，但是直到Barabási重新以现在的名字（[BA模型]）发现之后才开始受到关注的。根据这个过程，拥有更多入度的的网页相较一般网页会吸引更多的链接。这样的机制会产生幂律，但是这样的图和真实的网络图在其他特性上有所不同，例如没有紧密连接的小社群。人们开始提出和研究一些更加普适的模型和网络特性。例如Pachon（2018）等人提出了[https://en.wikipedia.org/wiki/Rich_get_richer 富者更富]模型的一个变式，它考量了两种不同的依附规则：偏好依附和仅对最新节点的均匀选择。<ref name="Pachon">Pachon, Shuyi, D (2018) [https://pattern.swarma.org/paper?id=41a5267e-7842-11ea-80cb-0242ac1a0005 "Scale-free behavior of networks with the copresence of preferential and uniform attachment rules"].Physica D: Nonlinear Phenomena.371.(1--12)</ref>
可以参考Dorogovtsev和Mendes的著作中对此的回顾。
Pennock等人对因特网链接提出了一个略有差别的生成模型。它们研究了对某一特定话题有兴趣的社群，如宇宙、上市公司、报纸或者科学家，并且弃用了因特网的一些主要枢纽。这个条件下，链接的分布不再是[[幂律分布]]而是更接近于[[正态分布]]。基于这些观测，作者提出了一个具有最低链接获得概率的择优依附生成模型。
另一个生成模型是Kumar等人研究的复制模型<ref>Kumar, Prabhakar (2000) [https://pattern.swarma.org/paper?id=3ffacbb6-7843-11ea-b88d-0242ac1a0005 Stochastic Models for the Web Graph].Foundations of Computer Science.(57--65)</ref>（2000），其中新节点会随机选择一个既存的节点并且复制它的部分链接。这样也会生成[[幂律分布]]。
有趣的是，网络的生长（添加新的节点）并不是产生无标度网络的必要条件。Dangalchev<ref name="Dangalchev">Ch, Dangalchev (2004) [https://pattern.swarma.org/paper?id=c992e5fc-7843-11ea-876f-0242ac1a0005 Generation models for scale-free networks].Physica A.</ref>（2004）给出了生成静态无标度网络的示例。Caldarelli（2002）等人提出，另一种可能方案是将结构作为静态，然后根据两个顶点间的某个特定性质建立连接。一旦对这些顶点确定了概率分布（适应度 fitnesses），在一些情景下静态网络也可以发展出无标度网络的特性。
==广义无标度模型==
对'''无标度网络'''的模拟曾爆发式地出现。Barabási和Albert<ref>A.-L. Barab, Albert, R. (1999) [https://pattern.swarma.org/paper?id=5f002f80-7841-11ea-9cca-0242ac1a0005 “Emergence of Scaling in Random Networks”].Science.286.(509--512)</ref>的成果之后出现了许多的变体<ref>Albert, R., Barabási, A.L. (2000) [https://pattern.swarma.org/paper?id=37358a32-7845-11ea-8898-0242ac1a0005 Topology of Evolving Networks: Local Events and Universality].Phys..85.24:</ref>
<ref>Mendes, Dorogovtsev S. N., J. F. F. (2002) [https://pattern.swarma.org/paper?id=0751449a-7846-11ea-b213-0242ac1a0005 Evolution of networks].Advances in Physics.51.(1079--1187)</ref>
<ref name="P. L. Krapivsky">P. L. Krapivsky, S. Redner, and F. Leyvraz (2000) [https://pattern.swarma.org/paper?id=7ab2c606-7847-11ea-a280-0242ac1a0005 Connectivity of Growing Random Networks].Phys. Rev. Lett..85.</ref>
<ref>Bosiljka Tadić (2001) [https://pattern.swarma.org/paper?id=5626b95e-7848-11ea-8cfc-0242ac1a0005 Dynamics of directed graphs: the world-wide Web].Physica A: Statistical Mechanics and its Applications.293.</ref>
<ref name="Pachon"/>
，几代的研究者，还有对过往数学成果的翻新。<ref>Herbert A. Simon (1955) [https://pattern.swarma.org/paper?id=8801fb0c-6eaa-11ea-9abf-0242ac1a0005 On a Class of Skew Distribution Functions].Biometrika.42.(10--440)</ref>只要模型中有[[幂律分布]]，那就是无标度网络，这个模型也即'''无标度模型'''。
===特征===
许多真实的网络都（近似）是无标度网络，因此需要无标度模型来描述它们。在普赖斯的体系里无标度模型需要两种组成部分：
1. 添加或者删除节点。通常我们更关注网络的生长，也就是添加节点。
2. [[偏好依附]]。新节点会连接到“旧”节点的概率 <math>\Pi</math> 。
请注意适应度模型（见下方），在不改变节点个数的前提下，也可以静态地运作。还有一点需要注意的是，尽管“偏好依附”模型会生成无标度网络，然而这并不能证明这就是真实世界演化的机制，毕竟也许现实世界有其他同样可以产生规模效应的机制。
===示例===
以下是一些生成无标度网络特性的模型：
====BA模型 The Barabási–Albert model====
第一个无标度模型[https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model BA模型]具有线性的偏好依附 <math> {\Pi} \left ( {k}_{i} \right )=\frac{{k}_{i}}{\sum _{j}{k}_{j}} </math> ，并且在每一步增加一个节点。
注意，现实网络中<math>\Pi \left ( k \right )</math>的属性是<math>\Pi \left ( k \right )\neq 0</math>，新节点依附于一个孤立节点个概率不是零。因此 <math>{\Pi} \left ({k}\right )</math> 的表达式为: <math>\Pi \left ( k \right )=A+k^{\alpha }</math> ，其中A是结点的初始吸引力。
====双层网络模型 Two-level network model====
Dangalchev<ref name="Dangalchev"/>通过添加二级偏好依附规则构建了一个双层模型。一个节点的吸引力是一个双层模型，不仅与和它相连接的节点的数量有关，也和和它二阶近邻的节点数量有关。
<math>{\Pi} \left ( k_{i} \right )=\frac{k_{i}+C\sum _{\left ( i,j \right )}k_{j}}{\sum _{j}k_{j}+C\sum _{j}k_{j}^{2}}</math>，其中C是介于0和1之间的系数。
====中介驱动依附模型 MDA model - mediation-driven attachment model====
在[https://en.wikipedia.org/wiki/Mediation-driven_attachment_model 中介依附模型]中，一个具有m条边的新节点会随机选择一个既存的被连接的节点，然后将它自己连接到该节点以及该节点的随机选择的邻居上。既存节点被选择成为连接对象的概率<math>{\Pi} \left ( {i} \right )</math>是 <math>{\Pi} \left ( {i} \right ) =\frac{k_{i}}{N}\frac{\sum _{k_{i}}^{j=1}\frac{1}{k_{j}}}{k_{i}}</math>，
其中因子 <math>\frac{{\sum} _{{k}_{i}}^{j=1}\frac{1}{{k}_{j}}}{{k}_{i}}</math> 是节点 <math>i</math> 的 <math>k_{i}</math> 个邻居的度的调和平均（IHM）的倒数。数值研究表明对于很大的 <math>N</math> 的 <math>{m}>14</math> 的调和平均数平均值会接近一个定值，也就是说 <math>{\Pi} \left ( {i} \right )\propto {k}_{i}</math>。
这暗示一个节点的链接数越高（度越高），它获得链接的概率也就越大，因为它们可以通过中介以多种方式被连接。这在直觉上体现了富者更富的的机制（或者说是BA模型中的偏好依附规则）。因此，中介依附网络看上去是遵从偏好依附规则的。<ref>Hassan, M. K., Islam, Syed (2017) [https://pattern.swarma.org/paper?id=027f2ee0-784c-11ea-9b35-0242ac1a0005 "Degree distribution, rank-size distribution, and leadership persistence in mediation-driven attachment networks"].Physica A.469.(23--30)</ref>
然而 <math>{m}=1</math> 时它表现为一个“赢家全赢”的机制，这时全部节点的99%都有数值为1的度，唯有一个节点是“超级富有”的。随着<math>m</math>值的增加“超级富有节点”和“贫穷节点”之间的差距会缩小，而当 <math>{m}>14</math> 时则发现会从“赢家全赢”转变到“富者更富”的机制。
====[[非线性偏好依附 Non-linear preferential attachment]]====
BA模型假设任意节点依附于节点i的概率 <math>{\Pi} \left ({k}\right )</math> 与节点 <math>{i}</math> 的[https://en.wikipedia.org/wiki/Degree_(graph_theory) 度] <math>k</math> 成正比。这个假设由两个假说构成，一是 <math>{\Pi} \left ({k}\right )</math> 由 <math>k</math> 决定，这与随机图中 <math>{\Pi} \left ({k}\right )=p</math> 形成对比，二是 <math>{\Pi} \left ({k}\right )</math> 是自变量为 <math>k</math> 的线性函数。<math>{\Pi} \left ({k}\right )</math>的精确形式不一定是线性的，并且当前研究表明度分布很大程度上由 <math>{\Pi} \left ({k}\right )</math> 决定。
Krapivsky、Redner和Leyvraz<ref name="P. L. Krapivsky"/>指出网络的无标度属性会被非线性的偏好依附破坏。唯一能让网络的拓扑结构具有无标度属性的情形是一个'''无限贴近线性 asymptotically linear'''的偏好依附，例如在 <math>{k}_{i}{\rightarrow} {\infty}</math> 时<math>\Pi \left ({k}_{i} \right )\sim \alpha _{\infty }{k}_{i}</math>。此时从这个比率等式可以得出
<math>\gamma =1+\frac{\mu}{\alpha _{\infty}}</math>，
这样一来度分布的指数便可以取任何介于2和<math>{\infty}</math>之间的值。
====层级网络模型 Hierarchical network model====
还有一种无标度网络，它的生长是遵循某种模式，比如[https://en.wikipedia.org/wiki/Hierarchical_network_model 层级网络模型]。<ref>Ravasz, E., Barabási (2003) [https://pattern.swarma.org/paper?id=61e6fa98-784c-11ea-8afb-0242ac1a0005 "Hierarchical organization in complex networks"].Phys. Rev. E, cond-mat/0206130. Bibcode:2003PhRvE..67b6112R. doi:10.1103/physreve.67.026112. PMID 12636753..67.(026112)</ref>
迭代式架构形成了一种层级网络。从完全连接的五个节点开始，构建与此四个一模一样的复制，将他们每一簇的外围节点与初始的那簇的中心节点相连接。由此我们便获得了一个25 个节点的网络（<math>N=25</math>）。重复相同的步骤，我们可以创建四个与初始那簇相同的四个复制，每个复制的四个外围节点再连接到第一个步骤中产生的四个簇的中心节点上。这样就获得了 <math>N=125</math> 的网络，并且步骤可以无限继续。
====适应度模型 Fitness model====
适应度模型不随机地以等概率 <math>p</math> 给两个顶点分配链接，而是为每一个顶点 <math>{j}</math> 设有一个内含的适合性 <math>x_{j}</math> ，让顶点 <math>{j}</math> 和顶点 <math>i</math> 之间的链接以概率<math>p\left ( x_{i},x_{j} \right )</math>产生。<ref>Caldarelli, G. (2002) [https://pattern.swarma.org/paper?id=3f815cb2-784e-11ea-a29b-0242ac1a0005 "Scale-free networks from varying vertex intrinsic fitness"].Phys. Rev. Lett.89.(258702, 2002PhRvL)</ref>在世界贸易网络中可以通过基于GDP的适应性来重建其中的网络特性，即：
<math>{p}\left ( {x}_{i},{x}_{j} \right )=\frac{\delta {x}_{i},{x}_{j} }{1+{\delta} {x}_{i},{x}_{j}}.</math><ref>Garlaschelli, D. (2004) [https://pattern.swarma.org/paper?id=89b3e2fa-784e-11ea-a064-0242ac1a0005 "Fitness-Dependent Topological Properties of the World Trade Web"].Phys. Rev. Lett.93.</ref>
====[[双曲几何图 Hyperbolic geometric graphs]]====
假设一个网络内含复杂网络双曲几何模型形状，那么可以用[https://en.wikipedia.org/wiki/Spatial_network 空间网络]生成无标度的度分布。这种混杂式的度分布体现了所含双曲几何形状[[双曲空间模型]]的负曲率和度量特性。<ref>Krioukov, Marián (2010) [https://pattern.swarma.org/paper?id=ee96c160-784e-11ea-a05d-0242ac1a0005 "Hyperbolic geometry of complex networks"].Physical.82.3:</ref>
==== 边缘变换以生成具有所需属性的无标度图 Edge dual transformation to generate scale free graphs with desired properties====
可以在低度相关性和聚类系数的无标度网络的基础上，通过应用边缘双变换来生成度相关性和聚类系数更高的新图。<ref name="Ramezanpour"/>
====均匀偏好依附模型 Uniform-Preferential-Attachment model(UPA)====
[https://en.wikipedia.org/w/index.php?title=UPA_model&action=edit&redlink=1 UPA模型]是偏好依附模型的一个变种（由Pachon等人提出），它运用了两种不同的依附规则：一个是体现富者更富的偏好依附机制（概率是 <math>1-p</math> ），还有一个是对最新的一些节点做均匀选择（概率是 <math>p</math> ）。这个改动对于研究度分布的无标度表现的鲁棒性有一些妙用。分析证明它依旧保留了近似幂律的度分布。<ref name="Pachon"/>
==[[无标度理想网络]]==
在[[ 网络理论]]中一个无标度理想网络是一个具有[https://en.wikipedia.org/wiki/Scale-Free_Ideal_Gas 无标度理想气体密度分布 scale-free ideal gas density distribution]的[https://en.wikipedia.org/wiki/Degree_distribution 度分布]的[[随机网络]]。当竞争性集群增长过程被应用于网络时，这些网络可以通过运用复杂网络的信息理论解译社交团体的规模分布来重现城市规模的分布和选举结果。<ref>Hernando; D. Villuendas, A., Vesperinas; M. Abad, C., Plastino (2009) [https://pattern.swarma.org/paper?id=46dd9d58-784f-11ea-a2bf-0242ac1a0005 "Unravelling the size distribution of social groups with information theory on complex networks"].Physical Journal B.</ref><ref>Moreira; Demétrius R. Paula; Raimundo N. Costa Filho; José S. Andrade, André A., Jr. (2006) [https://pattern.swarma.org/paper?id=bb782b24-784f-11ea-ad6b-0242ac1a0005 "Competitive cluster growth in complex networks"].Physical.73.</ref>在无标度理想网络模型中，可以展示[https://en.wikipedia.org/wiki/Six_degrees_of_separation 六度分离 six degrees of separation]现象的成因正是[[邓巴数]]。
==新特性==
对于一个具有n个节点和幂律指数<math>\beta >3</math>的无标度网络，其感应子图 induced subgraph由度大于<math>log\left ( n \right )\times log^{\ast }\left ( n \right )</math>的节点构成，是一个幂律指数<math>\beta'=2</math>的无标度网络。<ref>Hasan Heydari, S. Mahmoud Taheri, Kaveh Kavousi (2018) [https://pattern.swarma.org/paper?id=83be1d3c-7850-11ea-8cdd-0242ac1a0005 "Distributed Maximal Independent Set on Scale-Free Networks", 02513 [cs].Computer Science.</ref>
==相关内容==
*[https://en.wikipedia.org/wiki/Random_graph 随机图 Random Graph]
*[https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model]
*[https://en.wikipedia.org/wiki/Non-linear_preferential_attachment 非线性偏好依附 Non-linear preferential attachment]
*[https://en.wikipedia.org/wiki/Bose%E2%80%93Einstein_condensation:_a_network_theory_approach 玻色-爱因斯坦凝聚态：网络视角 Bose–Einstein condensation: a network theory approach]
*[https://en.wikipedia.org/wiki/Scale_invariance 规模不变性 Scale invariance]
*[[复杂网络 Complex network]]
*[https://en.wikipedia.org/wiki/Webgraph 网图 Webgraph]
*[[巴拉巴西-艾伯特模型 Barabási–Albert model]]
*[[比安科尼-巴拉巴西模型 Bianconi–Barabási model]]
==参考文献==
<references/>
==编者推荐==
[[File:无标度网络_推荐课程3.jpg|600px|thumb|right|[https://campus.swarma.org/play/coursedetail?id=10578 稳健又脆弱的无标度网络]]]
====[https://blog.csdn.net/itnerd/article/details/82965555 无标度网络的生成模型]====
该文采用由 Barabási 和 Albert 于 1999 年提出的增长网络网络模型（BA 模型），并使用matlab程序模拟了BA网络的演化过程。
===推荐课程===
====[https://campus.swarma.org/play/coursedetail?id=10404 图与网络：社交网络分析]====
社会网络、复杂网络都是复杂性科学研究的热门话题之一。该课程以「无标度网络」为例，讲解了社交网络及Barabasi-Albert模型，并教学Mathematica中关于网络的一系列工具。
====[https://campus.swarma.org/play/coursedetail?id=10578 稳健又脆弱的无标度网络]====
该课程将以无标度网络——复杂网络研究的典型代表为核心，了解复杂网络研究中的不同结构及其特点，现实中的无标度网络和其特点，以及无标度网络正反面效应。
====[https://campus.swarma.org/play/coursedetail?id=10587 从无标度网络研究历史看想法传播]====
该课程将从发现、建模和分析几个方面梳理无标度网络的研究历史，包括对于存在的争议的分析，最后给出对网络科学未来发展的一些看法。
----
本中文词条由 Entropie 参与编译，刘晶审校，欢迎在讨论页面留言。
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
[[category:复杂系统]]
|keywords =幂律分布,无标度网络,集智
|description =无标度性,依附模型,规模不变形
}}
'''无标度网络 scale-free network'''是一种[[度分布]]（即对复杂网络中节点度数的总体描述）服从或者接近[[幂律分布]]的[[复杂网络]]。无标度网络中某节点与另外 <math> k</math> 个节点相连接（度数为 <math>k</math> ）的概率是：
<center><div style="width:500px;height:30px">
<div style="float:left;width:400px"><math>P(k) \sim \ k^\boldsymbol{-\gamma}</math></div>
<div style="float:left;"><math>(1)</math></div></br>
</div></center>
其中， <math>{\gamma} </math> 是一个通常位于2和3之间的参数，但偶尔也会在这个区间之外。<ref>Onnela, J. -P., Saramaki, J., Hyvonen, J., Lazer, G., Kaski, D., Kertesz, K., Barabasi, J., A. -L. (2007) [https://pattern.swarma.org/paper?id=efb73d0a-7820-11ea-991e-0242ac1a0005 "Structure and tie strengths in mobile communication networks"].Proceedings of the National Academy of Sciences, doi:10.1073/pnas.0610245104. PMC 1863470. PMID 17456605..104.18:(7332--7336)</ref><ref>Krzysztof Choromański,Michał Matuszak,Jacek Miȩkisz (2013) [https://pattern.swarma.org/paper?id=086fb46c-6d95-11ea-bc89-0242ac1a0005 Scale-Free Graph with Preferential Attachment and Evolving Internal Vertex Structure].journal of statistical physics.151.6:(1175-1183)</ref>
许多网络似乎都体现出无标度的特性，然而统计分析却表明许多网络并不符合无标度特性。<ref name="Aaron Clauset">Aaron Clauset, Cosma Rohilla Shalizi, M E J Newman () [https://pattern.swarma.org/paper?id=88199410-6da6-11ea-b59a-0242ac1a0005 Power-Law Distributions in Empirical Data].51.4:(661-703)</ref><ref>Broido (2019) [https://pattern.swarma.org/paper?id=7e21863a-7822-11ea-ba18-0242ac1a0005 "Scale-free networks are rare"].Nature Communications.10.1:(1017)</ref>
[[偏好依附 preferential attachment]]和[https://en.wikipedia.org/wiki/Fitness_model_(network_theory) 适应度模型 fitness model]是对现实中的网络如何产生幂律度分布的可能解释。
==历史==
在对科学引文网的研究中，[[普赖斯 Derek de Solla Price]]在1965年发现：论文的链接数，即该论文被引用的次数，服从[https://en.wikipedia.org/wiki/Heavy-tailed_distribution 厚尾]的[https://en.wikipedia.org/wiki/Pareto_distribution 帕累托分布 Pareto distribution]或者[[幂律分布]]，由此得出引文网络是无标度的。然而他当时并未使用“无标度网络”这个术语。这个术语直到几十年之后才出现。在1976年的论文中，普赖斯还提出了一种解释引文网络产生[[幂律分布]]的机制，他称之为“累积优势 cumulative advantage”，也就是现今更被熟知的“[[偏好依附 preferential attachment]]”。
近期对无标度网络的关注始于1999年圣母大学的[https://en.wikipedia.org/wiki/Albert-L%C3%A1szl%C3%B3_Barab%C3%A1si 艾伯特-拉斯洛·巴拉巴西 Albert-László Barabási ]及其同事着手对部分万维网的拓扑结构进行绘制。<ref name="Barabási1999">Barabási, Réka. (1999) [https://pattern.swarma.org/paper?id=ced492e8-7822-11ea-8a27-0242ac1a0005 "Emergence of scaling in random networks"].Science.286.5439:(509--512)</ref>他们发现有些他们称之“'''枢纽 hubs'''”的节点比其他节点具有更多的链接数，同时网络任意节点的链接数服从[[幂律分布]]。在发现其他的网络，如部分社会网络和生物网络也具有厚尾的度分布之后，巴拉巴西及其同事创造了“无标度网络 Scale-free network”一词来描述这类度分布呈幂律的网络。Amaral等人指出，可以根据大k值的度分布的衰减，将大部分现实世界的网络归为两个大类。
巴拉巴西和艾伯特提出了一种他们称之为[[偏好依附 preferential attachment]]的生成机制，用来解释[[幂律分布]]，这基本上和普赖斯提出的机制相同。这种机制的解析解（也与普莱斯的相似）由Dorogovtsev，Mendes和Samukhin<>Dorogovtsev, S., Mendes, J., Samukhin, A. (2000) [https://pattern.swarma.org/paper?id=81070e4a-7824-11ea-8fd8-0242ac1a0005 "Structure of Growing Networks with Preferential Linking"].Physical Review Letters.85.21:(4633--4636)</ref>于2000年提出，Krapivsky，Redner和Leyvraz 等人也同时独立提出。后来由数学家[[贝拉·波洛巴斯 BélaBollobás]]严格证明。<ref>Bollobás, B., Riordan, O., Spencer, J., G. (2001) [https://pattern.swarma.org/paper?id=f16b5632-7824-11ea-9332-0242ac1a0005 "The degree sequence of a scale-free random graph process"].Random Structures and Algorithms.18.3:(279--290)</ref>
然而这种机制所生成的网络只是无标度网络这个大类中的特殊子集，许多其他机制自此也陆续被发现。<ref>Dorogovtsev, S. N., Mendes, J. F. F. (2002) [https://pattern.swarma.org/paper?id=4b0fcde6-7828-11ea-93d6-0242ac1a0005 "Evolution of networks"].Advances in Physics.51,.(1079--1187)</ref>
无标度网络的历史还存有一部分争议。在实证层面上，许多网络的无标度性被质疑。如Faloutsos三兄弟认为互联网是基于网络层错觉，实则是体现为高度节点的[https://en.wikipedia.org/wiki/Autonomous_system_(Internet) ASes]数据链结构。<ref>Willinger (2009) [https://pattern.swarma.org/paper?id=c60be3ae-7828-11ea-ab3c-0242ac1a0005 "Mathematics and the Internet: A Source of Enormous Confusion and Great Potential" (PDF). Notices of the AMS].American Mathematical Society.56.5:(586--599)</ref>
在理论层面上，研究者提出了对无标度的抽象定义的改良。例如李等人（2005）近日提供了更加准确的“无标度指标”。简而言之，定义 <math>G</math> 是具有连边集合E的图，顶点 <math>v</math> 的度（即与<math>v</math>邻接的边的数量）记为<math>deg\left ( v \right )</math>。定义：
<center><div style="width:500px;height:30px">
<div style="float:left;width:400px"><math>s(G) = \sum_{(u,v) \in E} \deg(u) \cdot \deg(v)</math></div>
<div style="float:left;"><math>(2)</math></div></br>
</div></center>
<math>s(G)</math>在高度节点与其他高度节点邻接时最大。定义：
<center><div style="width:500px;height:30px">
<div style="float:left;width:400px"><math>S(G) = \frac{s(G)}{s_\max}</math></div>
<div style="float:left;"><math>(3)</math></div></br>
</div></center>
其中，<math>{s}_{max}</math> 是所有与 <math>G</math> 的度分布相同的图的集合中图 <math>H</math> 的 <math>s(H)</math> 的最大值。 <math>S(G)</math> 是一个值域在0和1之间的指标，具有较小 <math>S(G)</math> 的图 <math>G</math> 是“丰标度”的，一个具有接近1的 <math>S(G)</math> 的图 <math>G</math> 是“无标度”的。这个定义体现了“无标度”所隐含的[[ 自相似性]]的概念。
==特征==
[[File:Scale-free_network_sample.png| 330px | thumb |right |随机网络（a）和无标度网络（b) 深色标记了无标度网络中的枢纽]]
[[File:Complex_network_degree_distribution_of_random_and_scale-free.png| 330px | thumb |right |随机和无标度复杂网络的度分布]]
无标度网络的特性是普遍存在度远高于平均值的节点。度最高的节点通常称为枢纽 hub，被认为在网络中起到特殊作用，尽管这还要看具体在网络的哪个区域。
无标度性与网络应对失败的鲁棒性有很大关系。主要的枢纽节点通常连接着小的枢纽节点。这些小的枢纽节点再伴随着度更小的节点，以此类推。这种层级关系使得网络能够[https://en.wikipedia.org/wiki/Fault-tolerance 容错 fault tolerant]行。如果错误随机发生，并且大量节点都具有较小的度，那么枢纽节点几乎不会受到影响。即便枢纽节点出现了错误，因为还有其他枢纽节点，网络通常不会失去原来的[https://en.wikipedia.org/wiki/Connectedness 连通性 connectedness]。然而，如果定向选择一些主要的枢纽节点并把它们从网络中去除，网络则会变为许多相对离散的图。因此，枢纽节点既是无标度网络的优势又是劣势。Cohen<ref>Cohen, K., Avraham, D., Havlin, S. (2000) [https://pattern.swarma.org/paper?id=ce02a3ee-7829-11ea-be52-0242ac1a0005 "Resilience of the Internet to Random Breakdowns"].Physical Review Letters.85.21:(4626--4628)</ref><ref>Cohen, K., Avraham, D., Havlin, S. (2001) [https://pattern.swarma.org/paper?id=523f6e44-782a-11ea-abd8-0242ac1a0005 ben-, "Breakdown of the Internet under Intentional Attack"].Physical Review Letters.86.16:(3682--3685)</ref>和Callaway<ref>Callaway, M. E. J., Watts, S. H., D. J. (2000) [https://pattern.swarma.org/paper?id=6ca146bc-782b-11ea-8cca-0242ac1a0005 "Network Robustness and Fragility: Percolation on Random Graphs"].Physical Review Letters.85.25:(5468--5471)</ref>等人曾用[[渗流理论 percolation theory]]分析过这些特性。
Cohen<ref>Cohen, K., Avraham, D., Havlin, S. (2000) [https://pattern.swarma.org/paper?id=ce02a3ee-7829-11ea-be52-0242ac1a0005 "Resilience of the Internet to Random Breakdowns"].Physical Review Letters.85.21:(4626--4628)</ref>证明对于大范围的无标度网络临界渗流阈值 critical percolation threshold， p_{c}=0.这表明从网络中随机删去任意数量的节点都不会破坏网络。这与 p_{c} =1/<math>\bar{k}</math>的Erdős–Rényi图形成了对比，其中 <math>\bar{k}</math> 是图的平均度。
无标度网络的另一个重要特性是随节点度数升高而降低的[[聚集系数 clustering coefficient]]分布。这个分布也服从[[幂律分布]]。这表明度数低的节点从属于致密的子图，这些子图再通过枢纽节点互相连接。试想一个社交网络，它的节点是人，而链接是熟人关系。很容易得出人们倾向于形成社群，也就是互相熟识的团体（可以将它理解为一个[https://en.wikipedia.org/wiki/Complete_graph 全连接图 complete graph ]）。另外这个小社群的人们也会有一些社群外的熟人关系。然而有些人与许多社群相连（如贵族、政治家）。这些人可以被认作是导致[[小世界现象 small-world phenomenon]]的缘由。
目前无标度网络的更具体的特性会根据他们不同的生成机制而改变。例如，由“偏好依附“生成的网络普遍将度较高的顶点放在网络的中央，将他们互相连接形成一个核心，由度逐渐降低的节点构成核心之间的区域以及外围。即便随机删除较大部分的顶点对网络整体的联通都不会有太大影响，这表明这种拓扑结构有利于提升安全性，尽管一些定向攻击会很快破坏其连通性。其他的一些将度较高的顶点放在外围的无标度网络并没有这样的性质。也就是说无标度网络的聚集系数会随着拓扑构造的改变而产生明显变化。
最后一个特性是关于网络中顶点之间的平均距离。对于大多数不规则网络，如[[小世界网络]]，这个距离相较于高度规则的[https://en.wikipedia.org/wiki/Lattice_graph 网格图]是非常小的。Cohen和Havlin证明了，2 < <math>{\gamma} </math> < 3的无关联幂律图会有非常小的半径<math>d\sim ln ln N</math>其中<math>N</math>是网络中节点的数量。<ref>Cohen, Shlomo (2003) [https://pattern.swarma.org/paper?id=3ecc6f3e-782e-11ea-8fc5-0242ac1a0005 "Scale-Free Networks Are Ultrasmall"].Physical Review Letters.90.5:</ref>
在实践中，一个生长中的无标度网络的半径几乎可以被认作是一个定值。
[[随机图]]的特性在图变形的过程中可能会变化也可能不变。正如Mashaghi A.等人所展示的，在一个将随机图转变为其双边图（或者线图）的过程中会产生一系列度分布近似，却提升了度相关性并且显著提升了聚集系数的图。<ref name="Ramezanpour">Ramezanpour, A., Karimipour, V., Mashaghi, A. (2003) [https://pattern.swarma.org/paper?id=bf724078-782e-11ea-890b-0242ac1a0005 "Generating correlated networks from uncorrelated ones"].Phys.67.4:</ref>
==示例==
[[File:Snapshot_of_weighted_stochastic_lattice.jpg|500px|缩略图|右|加权平面随机晶格 WPSL-weighted planar stochastic lattice]]
尽管许多真实世界的网络被认为是无标度的，然而其证明却往往因为愈发严格的数据分析技术而显得不够充分。<ref name="Aaron Clauset"></ref>由此，许多网络的无标度性还在科学社群中被讨论着。一些声称是无标度的网络包括：
• 社交网络包括合作网络。两个被广泛研究的示例是演员合演电影的合作网络和数学家合著论文的合作网络。
• 电脑网络包括互联网和万维网的网图。
• 一些金融网络，如银行间支付网络。<ref>De Masi (2006) [https://pattern.swarma.org/paper?id=223e74a0-7830-11ea-bd14-0242ac1a0005 "Fitness model for the Italian interbank money market"].Physical.74.6:</ref><ref>Soramäki (2007) [https://pattern.swarma.org/paper?id=969d3ce6-7830-11ea-8abd-0242ac1a0005 "The topology of interbank payment flows"].Physica A: Statistical Mechanics and Its Applications.379.1:(317--333)</ref>
• [https://en.wikipedia.org/wiki/Protein-protein_interaction 蛋白质-蛋白质相互作用 Protein-protein interaction]网络。
• [https://en.wikipedia.org/wiki/Semantic_network 语义网络 Semantic networks]。<ref>Steyvers, Tenenbaum (2005) [https://pattern.swarma.org/paper?id=af19837e-7835-11ea-a041-0242ac1a0005 "The Large-Scale Structure of Semantic Networks: Statistical Analyses and a Model of Semantic Growth"].Cognitive Science.29, 10.1:(41--78)</ref>
• 航空网络 Airline networks。
在高温超导体中也发现了无标度的拓扑结构。高温超导体<ref>Fratini (2010) [https://pattern.swarma.org/paper?id=f9f5e950-7835-11ea-840c-0242ac1a0005 "Scale-free structural organization of oxygen interstitials in La2CuO4+y"].Nature.466.7308:(841--844)</ref>
——其中电子服从量子物理，能够完美同步，零电阻地流动——似乎与看似随机的氧原子和晶格畸变的分形排列有关。<ref>Poccia, Aeppli (2012) [https://pattern.swarma.org/paper?id=383a505c-7836-11ea-b4f2-0242ac1a0005 "Optimum inhomogeneity of local lattice distortions in La2CuO4+y"].PNAS.109.39:(15685--15690)</ref>
近日发现，一种填充空间的元胞结构，[https://en.wikipedia.org/wiki/Weighted_planar_stochastic_lattice_(WPSL) 加权平面随机晶格]的配位数分布服从[[幂律分布]]。这暗示着晶格有一小部分区块，与它们公用边界的邻居的数量惊人地多。其构造由一个类似于将单位面积的正方形随机分割为四个区块发生器引发。于是这个发生器不断地被可用区块中的一个吸引，这个区块是从对应区域中择优选取的。这个动作将正方形划分为更小的互斥矩形块。通过用区块中心处的节点替换每个区块，再把区块间的公共边界替换为连接对应顶点的边，从而获得的WPSL（DWPSL）的对偶形成了一个度分布呈[[幂律分布]]的网络。<ref>Hassan, M. K., Hassan, M. Z., Pavel, N. I. (2010) [https://pattern.swarma.org/paper?id=fe62fb2c-783f-11ea-ac8c-0242ac1a0005 "Scale-free network topology and multifractality in a weighted planar stochastic lattice"].New Journal of Physics.12.9:</ref><ref>Hassan, M. K., Hassan, M. Z., Pavel, N. I. (2010) [https://pattern.swarma.org/paper?id=5f04729e-7840-11ea-9600-0242ac1a0005 "Scale-free coordination number disorder and multifractal size disorder in weighted planar stochastic lattice"].J. Phys.: Conf. Ser.297.(01)</ref>
它按照[https://en.wikipedia.org/wiki/Mediation-driven_attachment_model 中介驱动的依附模型 mediation-driven attachment model]规则生成，这看上去也体现着偏好依附的规则。
==构建模型==
无标度网络的出现不仅仅是时运使然。Erdős和Rényi (1960)研究了一种在每一个步骤中均匀地随机选择两个节点然后在他们之间加入链接的图生成模型。这些[[随机图]]中的特性与无标度网络很不一样，因此需要一种生成过程的模型。
最被熟知的无标度网络子集的生成模型是Barabási和Albert(1999)的[https://en.wikipedia.org/wiki/Rich_get_richer 富者更富 rich get richer]模型生成，它让每个网页根据一个非均匀的概率分布与既存网页建立连接，这个概率分布与当前网页的入度数成比例。这个模型最初由普赖斯在1965 年发明，并命名为累积优势，但是直到Barabási重新以现在的名字（[BA模型]）发现之后才开始受到关注的。根据这个过程，拥有更多入度的的网页相较一般网页会吸引更多的链接。这样的机制会产生幂律，但是这样的图和真实的网络图在其他特性上有所不同，例如没有紧密连接的小社群。人们开始提出和研究一些更加普适的模型和网络特性。例如Pachon（2018）等人提出了[https://en.wikipedia.org/wiki/Rich_get_richer 富者更富]模型的一个变式，它考量了两种不同的依附规则：偏好依附和仅对最新节点的均匀选择。<ref name="Pachon">Pachon, Shuyi, D (2018) [https://pattern.swarma.org/paper?id=41a5267e-7842-11ea-80cb-0242ac1a0005 "Scale-free behavior of networks with the copresence of preferential and uniform attachment rules"].Physica D: Nonlinear Phenomena.371.(1--12)</ref>
可以参考Dorogovtsev和Mendes的著作中对此的回顾。
Pennock等人对因特网链接提出了一个略有差别的生成模型。它们研究了对某一特定话题有兴趣的社群，如宇宙、上市公司、报纸或者科学家，并且弃用了因特网的一些主要枢纽。这个条件下，链接的分布不再是[[幂律分布]]而是更接近于[[正态分布]]。基于这些观测，作者提出了一个具有最低链接获得概率的择优依附生成模型。
另一个生成模型是Kumar等人研究的复制模型<ref>Kumar, Prabhakar (2000) [https://pattern.swarma.org/paper?id=3ffacbb6-7843-11ea-b88d-0242ac1a0005 Stochastic Models for the Web Graph].Foundations of Computer Science.(57--65)</ref>（2000），其中新节点会随机选择一个既存的节点并且复制它的部分链接。这样也会生成[[幂律分布]]。
有趣的是，网络的生长（添加新的节点）并不是产生无标度网络的必要条件。Dangalchev<ref name="Dangalchev">Ch, Dangalchev (2004) [https://pattern.swarma.org/paper?id=c992e5fc-7843-11ea-876f-0242ac1a0005 Generation models for scale-free networks].Physica A.</ref>（2004）给出了生成静态无标度网络的示例。Caldarelli（2002）等人提出，另一种可能方案是将结构作为静态，然后根据两个顶点间的某个特定性质建立连接。一旦对这些顶点确定了概率分布（适应度 fitnesses），在一些情景下静态网络也可以发展出无标度网络的特性。
==广义无标度模型==
对'''无标度网络'''的模拟曾爆发式地出现。Barabási和Albert<ref>A.-L. Barab, Albert, R. (1999) [https://pattern.swarma.org/paper?id=5f002f80-7841-11ea-9cca-0242ac1a0005 “Emergence of Scaling in Random Networks”].Science.286.(509--512)</ref>的成果之后出现了许多的变体<ref>Albert, R., Barabási, A.L. (2000) [https://pattern.swarma.org/paper?id=37358a32-7845-11ea-8898-0242ac1a0005 Topology of Evolving Networks: Local Events and Universality].Phys..85.24:</ref>
<ref>Mendes, Dorogovtsev S. N., J. F. F. (2002) [https://pattern.swarma.org/paper?id=0751449a-7846-11ea-b213-0242ac1a0005 Evolution of networks].Advances in Physics.51.(1079--1187)</ref>
<ref name="P. L. Krapivsky">P. L. Krapivsky, S. Redner, and F. Leyvraz (2000) [https://pattern.swarma.org/paper?id=7ab2c606-7847-11ea-a280-0242ac1a0005 Connectivity of Growing Random Networks].Phys. Rev. Lett..85.</ref>
<ref>Bosiljka Tadić (2001) [https://pattern.swarma.org/paper?id=5626b95e-7848-11ea-8cfc-0242ac1a0005 Dynamics of directed graphs: the world-wide Web].Physica A: Statistical Mechanics and its Applications.293.</ref>
<ref name="Pachon"/>
，几代的研究者，还有对过往数学成果的翻新。<ref>Herbert A. Simon (1955) [https://pattern.swarma.org/paper?id=8801fb0c-6eaa-11ea-9abf-0242ac1a0005 On a Class of Skew Distribution Functions].Biometrika.42.(10--440)</ref>只要模型中有[[幂律分布]]，那就是无标度网络，这个模型也即'''无标度模型'''。
===特征===
许多真实的网络都（近似）是无标度网络，因此需要无标度模型来描述它们。在普赖斯的体系里无标度模型需要两种组成部分：
1. 添加或者删除节点。通常我们更关注网络的生长，也就是添加节点。
2. [[偏好依附]]。新节点会连接到“旧”节点的概率 <math>\Pi</math> 。
请注意适应度模型（见下方），在不改变节点个数的前提下，也可以静态地运作。还有一点需要注意的是，尽管“偏好依附”模型会生成无标度网络，然而这并不能证明这就是真实世界演化的机制，毕竟也许现实世界有其他同样可以产生规模效应的机制。
===示例===
以下是一些生成无标度网络特性的模型：
====BA模型 The Barabási–Albert model====
第一个无标度模型[https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model BA模型]具有线性的偏好依附 <math> {\Pi} \left ( {k}_{i} \right )=\frac{{k}_{i}}{\sum _{j}{k}_{j}} </math> ，并且在每一步增加一个节点。
注意，现实网络中<math>\Pi \left ( k \right )</math>的属性是<math>\Pi \left ( k \right )\neq 0</math>，新节点依附于一个孤立节点个概率不是零。因此 <math>{\Pi} \left ({k}\right )</math> 的表达式为: <math>\Pi \left ( k \right )=A+k^{\alpha }</math> ，其中A是结点的初始吸引力。
====双层网络模型 Two-level network model====
Dangalchev<ref name="Dangalchev"/>通过添加二级偏好依附规则构建了一个双层模型。一个节点的吸引力是一个双层模型，不仅与和它相连接的节点的数量有关，也和和它二阶近邻的节点数量有关。
<math>{\Pi} \left ( k_{i} \right )=\frac{k_{i}+C\sum _{\left ( i,j \right )}k_{j}}{\sum _{j}k_{j}+C\sum _{j}k_{j}^{2}}</math>，其中C是介于0和1之间的系数。
====中介驱动依附模型 MDA model - mediation-driven attachment model====
在[https://en.wikipedia.org/wiki/Mediation-driven_attachment_model 中介依附模型]中，一个具有m条边的新节点会随机选择一个既存的被连接的节点，然后将它自己连接到该节点以及该节点的随机选择的邻居上。既存节点被选择成为连接对象的概率<math>{\Pi} \left ( {i} \right )</math>是 <math>{\Pi} \left ( {i} \right ) =\frac{k_{i}}{N}\frac{\sum _{k_{i}}^{j=1}\frac{1}{k_{j}}}{k_{i}}</math>，
其中因子 <math>\frac{{\sum} _{{k}_{i}}^{j=1}\frac{1}{{k}_{j}}}{{k}_{i}}</math> 是节点 <math>i</math> 的 <math>k_{i}</math> 个邻居的度的调和平均（IHM）的倒数。数值研究表明对于很大的 <math>N</math> 的 <math>{m}>14</math> 的调和平均数平均值会接近一个定值，也就是说 <math>{\Pi} \left ( {i} \right )\propto {k}_{i}</math>。
这暗示一个节点的链接数越高（度越高），它获得链接的概率也就越大，因为它们可以通过中介以多种方式被连接。这在直觉上体现了富者更富的的机制（或者说是BA模型中的偏好依附规则）。因此，中介依附网络看上去是遵从偏好依附规则的。<ref>Hassan, M. K., Islam, Syed (2017) [https://pattern.swarma.org/paper?id=027f2ee0-784c-11ea-9b35-0242ac1a0005 "Degree distribution, rank-size distribution, and leadership persistence in mediation-driven attachment networks"].Physica A.469.(23--30)</ref>
然而 <math>{m}=1</math> 时它表现为一个“赢家全赢”的机制，这时全部节点的99%都有数值为1的度，唯有一个节点是“超级富有”的。随着<math>m</math>值的增加“超级富有节点”和“贫穷节点”之间的差距会缩小，而当 <math>{m}>14</math> 时则发现会从“赢家全赢”转变到“富者更富”的机制。
====[[非线性偏好依附 Non-linear preferential attachment]]====
BA模型假设任意节点依附于节点i的概率 <math>{\Pi} \left ({k}\right )</math> 与节点 <math>{i}</math> 的[https://en.wikipedia.org/wiki/Degree_(graph_theory) 度] <math>k</math> 成正比。这个假设由两个假说构成，一是 <math>{\Pi} \left ({k}\right )</math> 由 <math>k</math> 决定，这与随机图中 <math>{\Pi} \left ({k}\right )=p</math> 形成对比，二是 <math>{\Pi} \left ({k}\right )</math> 是自变量为 <math>k</math> 的线性函数。<math>{\Pi} \left ({k}\right )</math>的精确形式不一定是线性的，并且当前研究表明度分布很大程度上由 <math>{\Pi} \left ({k}\right )</math> 决定。
Krapivsky、Redner和Leyvraz<ref name="P. L. Krapivsky"/>指出网络的无标度属性会被非线性的偏好依附破坏。唯一能让网络的拓扑结构具有无标度属性的情形是一个'''无限贴近线性 asymptotically linear'''的偏好依附，例如在 <math>{k}_{i}{\rightarrow} {\infty}</math> 时<math>\Pi \left ({k}_{i} \right )\sim \alpha _{\infty }{k}_{i}</math>。此时从这个比率等式可以得出
<math>\gamma =1+\frac{\mu}{\alpha _{\infty}}</math>，
这样一来度分布的指数便可以取任何介于2和<math>{\infty}</math>之间的值。
====层级网络模型 Hierarchical network model====
还有一种无标度网络，它的生长是遵循某种模式，比如[https://en.wikipedia.org/wiki/Hierarchical_network_model 层级网络模型]。<ref>Ravasz, E., Barabási (2003) [https://pattern.swarma.org/paper?id=61e6fa98-784c-11ea-8afb-0242ac1a0005 "Hierarchical organization in complex networks"].Phys. Rev. E, cond-mat/0206130. Bibcode:2003PhRvE..67b6112R. doi:10.1103/physreve.67.026112. PMID 12636753..67.(026112)</ref>
迭代式架构形成了一种层级网络。从完全连接的五个节点开始，构建与此四个一模一样的复制，将他们每一簇的外围节点与初始的那簇的中心节点相连接。由此我们便获得了一个25 个节点的网络（<math>N=25</math>）。重复相同的步骤，我们可以创建四个与初始那簇相同的四个复制，每个复制的四个外围节点再连接到第一个步骤中产生的四个簇的中心节点上。这样就获得了 <math>N=125</math> 的网络，并且步骤可以无限继续。
====适应度模型 Fitness model====
适应度模型不随机地以等概率 <math>p</math> 给两个顶点分配链接，而是为每一个顶点 <math>{j}</math> 设有一个内含的适合性 <math>x_{j}</math> ，让顶点 <math>{j}</math> 和顶点 <math>i</math> 之间的链接以概率<math>p\left ( x_{i},x_{j} \right )</math>产生。<ref>Caldarelli, G. (2002) [https://pattern.swarma.org/paper?id=3f815cb2-784e-11ea-a29b-0242ac1a0005 "Scale-free networks from varying vertex intrinsic fitness"].Phys. Rev. Lett.89.(258702, 2002PhRvL)</ref>在世界贸易网络中可以通过基于GDP的适应性来重建其中的网络特性，即：
<math>{p}\left ( {x}_{i},{x}_{j} \right )=\frac{\delta {x}_{i},{x}_{j} }{1+{\delta} {x}_{i},{x}_{j}}.</math><ref>Garlaschelli, D. (2004) [https://pattern.swarma.org/paper?id=89b3e2fa-784e-11ea-a064-0242ac1a0005 "Fitness-Dependent Topological Properties of the World Trade Web"].Phys. Rev. Lett.93.</ref>
====[[双曲几何图 Hyperbolic geometric graphs]]====
假设一个网络内含复杂网络双曲几何模型形状，那么可以用[https://en.wikipedia.org/wiki/Spatial_network 空间网络]生成无标度的度分布。这种混杂式的度分布体现了所含双曲几何形状[[双曲空间模型]]的负曲率和度量特性。<ref>Krioukov, Marián (2010) [https://pattern.swarma.org/paper?id=ee96c160-784e-11ea-a05d-0242ac1a0005 "Hyperbolic geometry of complex networks"].Physical.82.3:</ref>
==== 边缘变换以生成具有所需属性的无标度图 Edge dual transformation to generate scale free graphs with desired properties====
可以在低度相关性和聚类系数的无标度网络的基础上，通过应用边缘双变换来生成度相关性和聚类系数更高的新图。<ref name="Ramezanpour"/>
====均匀偏好依附模型 Uniform-Preferential-Attachment model(UPA)====
[https://en.wikipedia.org/w/index.php?title=UPA_model&action=edit&redlink=1 UPA模型]是偏好依附模型的一个变种（由Pachon等人提出），它运用了两种不同的依附规则：一个是体现富者更富的偏好依附机制（概率是 <math>1-p</math> ），还有一个是对最新的一些节点做均匀选择（概率是 <math>p</math> ）。这个改动对于研究度分布的无标度表现的鲁棒性有一些妙用。分析证明它依旧保留了近似幂律的度分布。<ref name="Pachon"/>
==[[无标度理想网络]]==
在[[ 网络理论]]中一个无标度理想网络是一个具有[https://en.wikipedia.org/wiki/Scale-Free_Ideal_Gas 无标度理想气体密度分布 scale-free ideal gas density distribution]的[https://en.wikipedia.org/wiki/Degree_distribution 度分布]的[[随机网络]]。当竞争性集群增长过程被应用于网络时，这些网络可以通过运用复杂网络的信息理论解译社交团体的规模分布来重现城市规模的分布和选举结果。<ref>Hernando; D. Villuendas, A., Vesperinas; M. Abad, C., Plastino (2009) [https://pattern.swarma.org/paper?id=46dd9d58-784f-11ea-a2bf-0242ac1a0005 "Unravelling the size distribution of social groups with information theory on complex networks"].Physical Journal B.</ref><ref>Moreira; Demétrius R. Paula; Raimundo N. Costa Filho; José S. Andrade, André A., Jr. (2006) [https://pattern.swarma.org/paper?id=bb782b24-784f-11ea-ad6b-0242ac1a0005 "Competitive cluster growth in complex networks"].Physical.73.</ref>在无标度理想网络模型中，可以展示[https://en.wikipedia.org/wiki/Six_degrees_of_separation 六度分离 six degrees of separation]现象的成因正是[[邓巴数]]。
==新特性==
对于一个具有n个节点和幂律指数<math>\beta >3</math>的无标度网络，其感应子图 induced subgraph由度大于<math>log\left ( n \right )\times log^{\ast }\left ( n \right )</math>的节点构成，是一个幂律指数<math>\beta'=2</math>的无标度网络。<ref>Hasan Heydari, S. Mahmoud Taheri, Kaveh Kavousi (2018) [https://pattern.swarma.org/paper?id=83be1d3c-7850-11ea-8cdd-0242ac1a0005 "Distributed Maximal Independent Set on Scale-Free Networks", 02513 [cs].Computer Science.</ref>
==相关内容==
*[https://en.wikipedia.org/wiki/Random_graph 随机图 Random Graph]
*[https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model Erdős–Rényi model]
*[https://en.wikipedia.org/wiki/Non-linear_preferential_attachment 非线性偏好依附 Non-linear preferential attachment]
*[https://en.wikipedia.org/wiki/Bose%E2%80%93Einstein_condensation:_a_network_theory_approach 玻色-爱因斯坦凝聚态：网络视角 Bose–Einstein condensation: a network theory approach]
*[https://en.wikipedia.org/wiki/Scale_invariance 规模不变性 Scale invariance]
*[[复杂网络 Complex network]]
*[https://en.wikipedia.org/wiki/Webgraph 网图 Webgraph]
*[[巴拉巴西-艾伯特模型 Barabási–Albert model]]
*[[比安科尼-巴拉巴西模型 Bianconi–Barabási model]]
==参考文献==
<references/>
==编者推荐==
[[File:无标度网络_推荐课程3.jpg|600px|thumb|right|[https://campus.swarma.org/play/coursedetail?id=10578 稳健又脆弱的无标度网络]]]
====[https://blog.csdn.net/itnerd/article/details/82965555 无标度网络的生成模型]====
该文采用由 Barabási 和 Albert 于 1999 年提出的增长网络网络模型（BA 模型），并使用matlab程序模拟了BA网络的演化过程。
===推荐课程===
====[https://campus.swarma.org/play/coursedetail?id=10404 图与网络：社交网络分析]====
社会网络、复杂网络都是复杂性科学研究的热门话题之一。该课程以「无标度网络」为例，讲解了社交网络及Barabasi-Albert模型，并教学Mathematica中关于网络的一系列工具。
====[https://campus.swarma.org/play/coursedetail?id=10578 稳健又脆弱的无标度网络]====
该课程将以无标度网络——复杂网络研究的典型代表为核心，了解复杂网络研究中的不同结构及其特点，现实中的无标度网络和其特点，以及无标度网络正反面效应。
====[https://campus.swarma.org/play/coursedetail?id=10587 从无标度网络研究历史看想法传播]====
该课程将从发现、建模和分析几个方面梳理无标度网络的研究历史，包括对于存在的争议的分析，最后给出对网络科学未来发展的一些看法。
----
本中文词条由 Entropie 参与编译，刘晶审校，欢迎在讨论页面留言。
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
[[category:复杂系统]]