无标度网络

无标度网络 scale-free network是一种度分布（即对复杂网络中节点度数的总体描述）服从或者接近幂律分布的复杂网络。无标度网络中某节点与另外 [math]\displaystyle{ k }[/math] 个节点相连接（度数为 [math]\displaystyle{ k }[/math] ）的概率是：

[math]\displaystyle{ P(k) \sim \ k^\boldsymbol{-\gamma} }[/math]

[math]\displaystyle{ (1) }[/math]

其中， [math]\displaystyle{ {\gamma} }[/math] 是一个通常位于2和3之间的参数，但偶尔也会在这个区间之外。

许多网络似乎都体现出无标度的特性，然而统计分析却表明许多网络并不符合无标度特性。 偏好依附 preferential attachment和适应度模型 fitness model是对现实中的网络如何产生幂律度分布的可能解释。

历史

在对科学引文网的研究中，普赖斯 Derek de Solla Price在1965年发现：论文的链接数，即该论文被引用的次数，服从厚尾的帕累托分布 Pareto distribution或者幂律分布，由此得出引文网络是无标度的。然而他当时并未使用“无标度网络”这个术语。这个术语直到几十年之后才出现。在1976年的论文中，普赖斯还提出了一种解释引文网络产生幂律分布的机制，他称之为“累积优势 cumulative advantage”，也就是现今更被熟知的“偏好依附 preferential attachment”。

近期对无标度网络的关注始于1999年圣母大学的艾伯特-拉斯洛·巴拉巴西 Albert-László Barabási 及其同事着手对部分万维网的拓扑结构进行绘制。他们发现有些他们称之“枢纽 hubs”的节点比其他节点具有更多的链接数，同时网络任意节点的链接数服从幂律分布。在发现其他的网络，如部分社会网络和生物网络也具有厚尾的度分布之后，巴拉巴西及其同事创造了“无标度网络 Scale-free network”一词来描述这类度分布呈幂律的网络。Amaral等人指出，可以根据大k值的度分布的衰减，将大部分现实世界的网络归为两个大类。

巴拉巴西和艾伯特提出了一种他们称之为偏好依附 preferential attachment的生成机制，用来解释幂律分布，这基本上和普赖斯提出的机制相同。这种机制的解析解（也与普莱斯的相似）由Dorogovtsev，Mendes和Samukhin<>Dorogovtsev, S., Mendes, J., Samukhin, A. (2000) "Structure of Growing Networks with Preferential Linking".Physical Review Letters.85.21:(4633--4636)</ref>于2000年提出，Krapivsky，Redner和Leyvraz 等人也同时独立提出。后来由数学家贝拉·波洛巴斯 BélaBollobás严格证明。 然而这种机制所生成的网络只是无标度网络这个大类中的特殊子集，许多其他机制自此也陆续被发现。

无标度网络的历史还存有一部分争议。在实证层面上，许多网络的无标度性被质疑。如Faloutsos三兄弟认为互联网是基于网络层错觉，实则是体现为高度节点的ASes数据链结构。

在理论层面上，研究者提出了对无标度的抽象定义的改良。例如李等人（2005）近日提供了更加准确的“无标度指标”。简而言之，定义 [math]\displaystyle{ G }[/math] 是具有连边集合E的图，顶点 [math]\displaystyle{ v }[/math] 的度（即与[math]\displaystyle{ v }[/math]邻接的边的数量）记为[math]\displaystyle{ deg\left ( v \right ) }[/math]。定义：

[math]\displaystyle{ s(G) = \sum_{(u,v) \in E} \deg(u) \cdot \deg(v) }[/math]

[math]\displaystyle{ (2) }[/math]

[math]\displaystyle{ s(G) }[/math]在高度节点与其他高度节点邻接时最大。定义：

[math]\displaystyle{ S(G) = \frac{s(G)}{s_\max} }[/math]

[math]\displaystyle{ (3) }[/math]

其中，[math]\displaystyle{ {s}_{max} }[/math] 是所有与 [math]\displaystyle{ G }[/math] 的度分布相同的图的集合中图 [math]\displaystyle{ H }[/math] 的 [math]\displaystyle{ s(H) }[/math] 的最大值。 [math]\displaystyle{ S(G) }[/math] 是一个值域在0和1之间的指标，具有较小 [math]\displaystyle{ S(G) }[/math] 的图 [math]\displaystyle{ G }[/math] 是“丰标度”的，一个具有接近1的 [math]\displaystyle{ S(G) }[/math] 的图 [math]\displaystyle{ G }[/math] 是“无标度”的。这个定义体现了“无标度”所隐含的自相似性的概念。

特征

随机网络（a）和无标度网络（b) 深色标记了无标度网络中的枢纽

随机和无标度复杂网络的度分布

无标度网络的特性是普遍存在度远高于平均值的节点。度最高的节点通常称为枢纽 hub，被认为在网络中起到特殊作用，尽管这还要看具体在网络的哪个区域。

无标度性与网络应对失败的鲁棒性有很大关系。主要的枢纽节点通常连接着小的枢纽节点。这些小的枢纽节点再伴随着度更小的节点，以此类推。这种层级关系使得网络能够容错 fault tolerant行。如果错误随机发生，并且大量节点都具有较小的度，那么枢纽节点几乎不会受到影响。即便枢纽节点出现了错误，因为还有其他枢纽节点，网络通常不会失去原来的连通性 connectedness。然而，如果定向选择一些主要的枢纽节点并把它们从网络中去除，网络则会变为许多相对离散的图。因此，枢纽节点既是无标度网络的优势又是劣势。Cohen和Callaway等人曾用渗流理论 percolation theory分析过这些特性。 Cohen证明对于大范围的无标度网络临界渗流阈值 critical percolation threshold， p_{c}=0.这表明从网络中随机删去任意数量的节点都不会破坏网络。这与 p_{c} =1/[math]\displaystyle{ \bar{k} }[/math]的Erdős–Rényi图形成了对比，其中 [math]\displaystyle{ \bar{k} }[/math] 是图的平均度。

无标度网络的另一个重要特性是随节点度数升高而降低的聚集系数 clustering coefficient分布。这个分布也服从幂律分布。这表明度数低的节点从属于致密的子图，这些子图再通过枢纽节点互相连接。试想一个社交网络，它的节点是人，而链接是熟人关系。很容易得出人们倾向于形成社群，也就是互相熟识的团体（可以将它理解为一个全连接图 complete graph ）。另外这个小社群的人们也会有一些社群外的熟人关系。然而有些人与许多社群相连（如贵族、政治家）。这些人可以被认作是导致小世界现象 small-world phenomenon的缘由。

目前无标度网络的更具体的特性会根据他们不同的生成机制而改变。例如，由“偏好依附“生成的网络普遍将度较高的顶点放在网络的中央，将他们互相连接形成一个核心，由度逐渐降低的节点构成核心之间的区域以及外围。即便随机删除较大部分的顶点对网络整体的联通都不会有太大影响，这表明这种拓扑结构有利于提升安全性，尽管一些定向攻击会很快破坏其连通性。其他的一些将度较高的顶点放在外围的无标度网络并没有这样的性质。也就是说无标度网络的聚集系数会随着拓扑构造的改变而产生明显变化。

最后一个特性是关于网络中顶点之间的平均距离。对于大多数不规则网络，如小世界网络，这个距离相较于高度规则的网格图是非常小的。Cohen和Havlin证明了，2 < [math]\displaystyle{ {\gamma} }[/math] < 3的无关联幂律图会有非常小的半径[math]\displaystyle{ d\sim ln ln N }[/math]其中[math]\displaystyle{ N }[/math]是网络中节点的数量。 在实践中，一个生长中的无标度网络的半径几乎可以被认作是一个定值。

随机图的特性在图变形的过程中可能会变化也可能不变。正如Mashaghi A.等人所展示的，在一个将随机图转变为其双边图（或者线图）的过程中会产生一系列度分布近似，却提升了度相关性并且显著提升了聚集系数的图。

示例

加权平面随机晶格 WPSL-weighted planar stochastic lattice

尽管许多真实世界的网络被认为是无标度的，然而其证明却往往因为愈发严格的数据分析技术而显得不够充分。由此，许多网络的无标度性还在科学社群中被讨论着。一些声称是无标度的网络包括：

• 社交网络包括合作网络。两个被广泛研究的示例是演员合演电影的合作网络和数学家合著论文的合作网络。

• 电脑网络包括互联网和万维网的网图。

• 一些金融网络，如银行间支付网络。

• 蛋白质-蛋白质相互作用 Protein-protein interaction网络。

• 语义网络 Semantic networks。

• 航空网络 Airline networks。

在高温超导体中也发现了无标度的拓扑结构。高温超导体 ——其中电子服从量子物理，能够完美同步，零电阻地流动——似乎与看似随机的氧原子和晶格畸变的分形排列有关。

近日发现，一种填充空间的元胞结构，加权平面随机晶格的配位数分布服从幂律分布。这暗示着晶格有一小部分区块，与它们公用边界的邻居的数量惊人地多。其构造由一个类似于将单位面积的正方形随机分割为四个区块发生器引发。于是这个发生器不断地被可用区块中的一个吸引，这个区块是从对应区域中择优选取的。这个动作将正方形划分为更小的互斥矩形块。通过用区块中心处的节点替换每个区块，再把区块间的公共边界替换为连接对应顶点的边，从而获得的WPSL（DWPSL）的对偶形成了一个度分布呈幂律分布的网络。 它按照中介驱动的依附模型 mediation-driven attachment model规则生成，这看上去也体现着偏好依附的规则。

构建模型

无标度网络的出现不仅仅是时运使然。Erdős和Rényi (1960)研究了一种在每一个步骤中均匀地随机选择两个节点然后在他们之间加入链接的图生成模型。这些随机图中的特性与无标度网络很不一样，因此需要一种生成过程的模型。

最被熟知的无标度网络子集的生成模型是Barabási和Albert(1999)的富者更富 rich get richer模型生成，它让每个网页根据一个非均匀的概率分布与既存网页建立连接，这个概率分布与当前网页的入度数成比例。这个模型最初由普赖斯在1965 年发明，并命名为累积优势，但是直到Barabási重新以现在的名字（[BA模型]）发现之后才开始受到关注的。根据这个过程，拥有更多入度的的网页相较一般网页会吸引更多的链接。这样的机制会产生幂律，但是这样的图和真实的网络图在其他特性上有所不同，例如没有紧密连接的小社群。人们开始提出和研究一些更加普适的模型和网络特性。例如Pachon（2018）等人提出了富者更富模型的一个变式，它考量了两种不同的依附规则：偏好依附和仅对最新节点的均匀选择。 可以参考Dorogovtsev和Mendes的著作中对此的回顾。

Pennock等人对因特网链接提出了一个略有差别的生成模型。它们研究了对某一特定话题有兴趣的社群，如宇宙、上市公司、报纸或者科学家，并且弃用了因特网的一些主要枢纽。这个条件下，链接的分布不再是幂律分布而是更接近于正态分布。基于这些观测，作者提出了一个具有最低链接获得概率的择优依附生成模型。

另一个生成模型是Kumar等人研究的复制模型（2000），其中新节点会随机选择一个既存的节点并且复制它的部分链接。这样也会生成幂律分布。

有趣的是，网络的生长（添加新的节点）并不是产生无标度网络的必要条件。Dangalchev（2004）给出了生成静态无标度网络的示例。Caldarelli（2002）等人提出，另一种可能方案是将结构作为静态，然后根据两个顶点间的某个特定性质建立连接。一旦对这些顶点确定了概率分布（适应度 fitnesses），在一些情景下静态网络也可以发展出无标度网络的特性。

广义无标度模型

对无标度网络的模拟曾爆发式地出现。Barabási和Albert的成果之后出现了许多的变体 ，几代的研究者，还有对过往数学成果的翻新。只要模型中有幂律分布，那就是无标度网络，这个模型也即无标度模型。

特征

许多真实的网络都（近似）是无标度网络，因此需要无标度模型来描述它们。在普赖斯的体系里无标度模型需要两种组成部分：

1. 添加或者删除节点。通常我们更关注网络的生长，也就是添加节点。

2. 偏好依附。新节点会连接到“旧”节点的概率 [math]\displaystyle{ \Pi }[/math] 。

请注意适应度模型（见下方），在不改变节点个数的前提下，也可以静态地运作。还有一点需要注意的是，尽管“偏好依附”模型会生成无标度网络，然而这并不能证明这就是真实世界演化的机制，毕竟也许现实世界有其他同样可以产生规模效应的机制。

示例

以下是一些生成无标度网络特性的模型：

BA模型 The Barabási–Albert model

第一个无标度模型BA模型具有线性的偏好依附 [math]\displaystyle{ {\Pi} \left ( {k}_{i} \right )=\frac{{k}_{i}}{\sum _{j}{k}_{j}} }[/math] ，并且在每一步增加一个节点。

注意，现实网络中[math]\displaystyle{ \Pi \left ( k \right ) }[/math]的属性是[math]\displaystyle{ \Pi \left ( k \right )\neq 0 }[/math]，新节点依附于一个孤立节点个概率不是零。因此 [math]\displaystyle{ {\Pi} \left ({k}\right ) }[/math] 的表达式为: [math]\displaystyle{ \Pi \left ( k \right )=A+k^{\alpha } }[/math] ，其中A是结点的初始吸引力。

双层网络模型 Two-level network model

Dangalchev通过添加二级偏好依附规则构建了一个双层模型。一个节点的吸引力是一个双层模型，不仅与和它相连接的节点的数量有关，也和和它二阶近邻的节点数量有关。 [math]\displaystyle{ {\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

在中介依附模型中，一个具有m条边的新节点会随机选择一个既存的被连接的节点，然后将它自己连接到该节点以及该节点的随机选择的邻居上。既存节点被选择成为连接对象的概率[math]\displaystyle{ {\Pi} \left ( {i} \right ) }[/math]是 [math]\displaystyle{ {\Pi} \left ( {i} \right ) =\frac{k_{i}}{N}\frac{\sum _{k_{i}}^{j=1}\frac{1}{k_{j}}}{k_{i}} }[/math]， 其中因子 [math]\displaystyle{ \frac{{\sum} _{{k}_{i}}^{j=1}\frac{1}{{k}_{j}}}{{k}_{i}} }[/math] 是节点 [math]\displaystyle{ i }[/math] 的 [math]\displaystyle{ k_{i} }[/math] 个邻居的度的调和平均（IHM）的倒数。数值研究表明对于很大的 [math]\displaystyle{ N }[/math] 的 [math]\displaystyle{ {m}\gt 14 }[/math] 的调和平均数平均值会接近一个定值，也就是说 [math]\displaystyle{ {\Pi} \left ( {i} \right )\propto {k}_{i} }[/math]。

这暗示一个节点的链接数越高（度越高），它获得链接的概率也就越大，因为它们可以通过中介以多种方式被连接。这在直觉上体现了富者更富的的机制（或者说是BA模型中的偏好依附规则）。因此，中介依附网络看上去是遵从偏好依附规则的。

然而 [math]\displaystyle{ {m}=1 }[/math] 时它表现为一个“赢家全赢”的机制，这时全部节点的99%都有数值为1的度，唯有一个节点是“超级富有”的。随着[math]\displaystyle{ m }[/math]值的增加“超级富有节点”和“贫穷节点”之间的差距会缩小，而当 [math]\displaystyle{ {m}\gt 14 }[/math] 时则发现会从“赢家全赢”转变到“富者更富”的机制。

非线性偏好依附 Non-linear preferential attachment

BA模型假设任意节点依附于节点i的概率 [math]\displaystyle{ {\Pi} \left ({k}\right ) }[/math] 与节点 [math]\displaystyle{ {i} }[/math] 的度 [math]\displaystyle{ k }[/math] 成正比。这个假设由两个假说构成，一是 [math]\displaystyle{ {\Pi} \left ({k}\right ) }[/math] 由 [math]\displaystyle{ k }[/math] 决定，这与随机图中 [math]\displaystyle{ {\Pi} \left ({k}\right )=p }[/math] 形成对比，二是 [math]\displaystyle{ {\Pi} \left ({k}\right ) }[/math] 是自变量为 [math]\displaystyle{ k }[/math] 的线性函数。[math]\displaystyle{ {\Pi} \left ({k}\right ) }[/math]的精确形式不一定是线性的，并且当前研究表明度分布很大程度上由 [math]\displaystyle{ {\Pi} \left ({k}\right ) }[/math] 决定。

Krapivsky、Redner和Leyvraz指出网络的无标度属性会被非线性的偏好依附破坏。唯一能让网络的拓扑结构具有无标度属性的情形是一个无限贴近线性 asymptotically linear的偏好依附，例如在 [math]\displaystyle{ {k}_{i}{\rightarrow} {\infty} }[/math] 时[math]\displaystyle{ \Pi \left ({k}_{i} \right )\sim \alpha _{\infty }{k}_{i} }[/math]。此时从这个比率等式可以得出 [math]\displaystyle{ \gamma =1+\frac{\mu}{\alpha _{\infty}} }[/math]， 这样一来度分布的指数便可以取任何介于2和[math]\displaystyle{ {\infty} }[/math]之间的值。

层级网络模型 Hierarchical network model

还有一种无标度网络，它的生长是遵循某种模式，比如层级网络模型。

迭代式架构形成了一种层级网络。从完全连接的五个节点开始，构建与此四个一模一样的复制，将他们每一簇的外围节点与初始的那簇的中心节点相连接。由此我们便获得了一个25 个节点的网络（[math]\displaystyle{ N=25 }[/math]）。重复相同的步骤，我们可以创建四个与初始那簇相同的四个复制，每个复制的四个外围节点再连接到第一个步骤中产生的四个簇的中心节点上。这样就获得了 [math]\displaystyle{ N=125 }[/math] 的网络，并且步骤可以无限继续。

适应度模型 Fitness model

适应度模型不随机地以等概率 [math]\displaystyle{ p }[/math] 给两个顶点分配链接，而是为每一个顶点 [math]\displaystyle{ {j} }[/math] 设有一个内含的适合性 [math]\displaystyle{ x_{j} }[/math] ，让顶点 [math]\displaystyle{ {j} }[/math] 和顶点 [math]\displaystyle{ i }[/math] 之间的链接以概率[math]\displaystyle{ p\left ( x_{i},x_{j} \right ) }[/math]产生。在世界贸易网络中可以通过基于GDP的适应性来重建其中的网络特性，即： [math]\displaystyle{ {p}\left ( {x}_{i},{x}_{j} \right )=\frac{\delta {x}_{i},{x}_{j} }{1+{\delta} {x}_{i},{x}_{j}}. }[/math]

双曲几何图 Hyperbolic geometric graphs

假设一个网络内含复杂网络双曲几何模型形状，那么可以用空间网络生成无标度的度分布。这种混杂式的度分布体现了所含双曲几何形状双曲空间模型的负曲率和度量特性。

边缘变换以生成具有所需属性的无标度图 Edge dual transformation to generate scale free graphs with desired properties

可以在低度相关性和聚类系数的无标度网络的基础上，通过应用边缘双变换来生成度相关性和聚类系数更高的新图。

均匀偏好依附模型 Uniform-Preferential-Attachment model(UPA)

UPA模型是偏好依附模型的一个变种（由Pachon等人提出），它运用了两种不同的依附规则：一个是体现富者更富的偏好依附机制（概率是 [math]\displaystyle{ 1-p }[/math] ），还有一个是对最新的一些节点做均匀选择（概率是 [math]\displaystyle{ p }[/math] ）。这个改动对于研究度分布的无标度表现的鲁棒性有一些妙用。分析证明它依旧保留了近似幂律的度分布。

无标度理想网络

在网络理论中一个无标度理想网络是一个具有无标度理想气体密度分布 scale-free ideal gas density distribution的度分布的随机网络。当竞争性集群增长过程被应用于网络时，这些网络可以通过运用复杂网络的信息理论解译社交团体的规模分布来重现城市规模的分布和选举结果。在无标度理想网络模型中，可以展示六度分离 six degrees of separation现象的成因正是邓巴数。

新特性

对于一个具有n个节点和幂律指数[math]\displaystyle{ \beta \gt 3 }[/math]的无标度网络，其感应子图 induced subgraph由度大于[math]\displaystyle{ log\left ( n \right )\times log^{\ast }\left ( n \right ) }[/math]的节点构成，是一个幂律指数[math]\displaystyle{ \beta'=2 }[/math]的无标度网络。

相关内容

• 随机图 Random Graph

• Erdős–Rényi model

• 非线性偏好依附 Non-linear preferential attachment

• 玻色-爱因斯坦凝聚态：网络视角 Bose–Einstein condensation: a network theory approach

• 规模不变性 Scale invariance

• 复杂网络 Complex network

• 网图 Webgraph

• 巴拉巴西-艾伯特模型 Barabási–Albert model

• 比安科尼-巴拉巴西模型 Bianconi–Barabási model

编者推荐

稳健又脆弱的无标度网络

无标度网络的生成模型

该文采用由 Barabási 和 Albert 于 1999 年提出的增长网络网络模型（BA 模型），并使用matlab程序模拟了BA网络的演化过程。

推荐课程

图与网络：社交网络分析

社会网络、复杂网络都是复杂性科学研究的热门话题之一。该课程以「无标度网络」为例，讲解了社交网络及Barabasi-Albert模型，并教学Mathematica中关于网络的一系列工具。

稳健又脆弱的无标度网络

该课程将以无标度网络——复杂网络研究的典型代表为核心，了解复杂网络研究中的不同结构及其特点，现实中的无标度网络和其特点，以及无标度网络正反面效应。

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

该课程将从发现、建模和分析几个方面梳理无标度网络的研究历史，包括对于存在的争议的分析，最后给出对网络科学未来发展的一些看法。

重访经典：无标度网络

该课程解读的是Barabasi的大作，主要介绍了网络中的幂律分布特性，首次介绍了无标度网络这一重要概念，并研究了其背后的生成机制——偏好连接(preferential attachment)。

---

本中文词条由Entropie参与编译，刘晶审校，薄荷编辑，欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。