强无标度网络在现实网络中的罕见性
论文作者：Anna D. Broido, Aaron Clauset（科罗拉多大学波德分校）
论文链接：https://www.nature.com/articles/s41467-019-08746-5
源码链接：https://github.com/adbroido/SFAnalysis
前言
现实世界中的网络通常声称是无标度的，这意味着节点度k遵循着幂律分布k^-α，这对复杂系统的结构和动力学具有非常广泛的影响。但是，无标度网络的普遍性是存在争议的。在本论文中，定义了无标度网络的不同衡量尺度，并将其应用于近1000个社会、生物、技术、交通和信息等网络中，对其无经验性进行了严格的检验。
在这些网络中，本文发现，从经验上讲，有着高度无尺度性质的网络结构很少见，而对大多数网络而言，对数正态分布拟合数据的能力与幂律分布一样好，有时甚至更好。而且，实验表明，社交网络充其量只是弱无标度的，而只有少数技术和生物网络是无标度的。
背景介绍网络是表示和研究复杂系统结构的有力方法。
个人之间的社会互动，生物有机体中蛋白质或基因的互动，数字计算机之间的交流以及各种运输系统等等都是网络作为研究手段的例子。在整个科学领域和网络类别中，通常都会遇到这样的说法：大多数或所有现实世界网络都是无标度的。一般，如果节点度k遵循幂律分布k^-α，其中α＞1则认为这样的网络是无标度网络。当然，有一些版本中会需要更多的要求，例如需要2＜α＜3或者节点度的演变符合优先连接机制。
无标度网络的研究和应用在网络科学中是很普遍的，许多研究调查了无标度结构的存在是如何影响在网络上的动态运行，无标度网络也被广泛用作基于网络的数值模拟和实验的基础。然而，无标度网络存在的普遍性仍然存在争议，已有许多研究表明了对它普遍性存在的支持，但仍存在许多统计或理论方面的挑战。
导致这些冲突观点存在的原因包括：之前的工作中通常依赖的是较小的、特定领域的数据集；不太严格的统计方法；“无标度”结构的不同定义以及不清楚哪些可以作为衡量无标度网络存在的标准等等。此外，也很少有研究对拟合的幂律分布与可替代的无标度分布（例如正态分布或拉伸指数分布）进行严格的比较。
为了解决这些冲突，本文进行严格测试，通过将最先进的统计方法应用于大量不同的现实网络来解决无标度网络的普遍性。
为了明确涵盖之前研究中无标度网络定义方式的各种变化，本文形式化了一组定量标准，这些标准代表了特定网络中无标度结构的不同强度。对语料库中的每个网络数据集，我们估计最合适的幂律分布模型，测试其统计合理性，并将其与其他非无标度分布进行比较。最后我们分析这些结果，考虑无标度结构的证据如何在各个域之间变化，并在几种替代标准下定量评估其稳健性。最后，我们给出了对之后研究的讨论和对未来网络结构的发展的一些建议。
实验准备本文使用的语料库由928个网络数据集组成，这些数据集来自ICON，涵盖生物学、信息、社会、技术和运输领域的网络，其范围从数百个节点到数百万个节点不等。下图展示的是该数据集中平均度和节点数量n之间的函数。为确定哪些度分布是可用的度分布，本文首先应用一系列图形转换，将给定的网络数据集转换为一组简单图，每个简单图都可以明确测试无标度结构。此过程中，在预先指定阈值下过于密集或稀疏的简单图将被舍弃。
然后，对每个简单图应用标准统计方法来定义度右尾分布的最佳拟合幂律分布，并用拟合优度检验评估其统计合理性，同时使用似然比检验将四个可替代的分布拟合到右尾的相同部分来进行比较。
无标度网络的定义一个分布被定义为无标度结构通常有以下两种情况：（i）幂律分布不一定是度分布的最好模型，但它相对来说比可替代分布会更好；（ii）幂律分布本身就是最好的度分布的最好的模型。
对于第一种情况，可被归类为：1. 超弱：对于至少50%的图形，没有其他分布优于幂律分布。对于第二种情况，可被归类为以下三种：1. 最弱：对于至少50%的图，幂律分布不能被拒绝(p ≧ 0.1)；2. 弱：在最弱的要求上，幂律分布区域至少包含50个节点；3. 强：在弱和最弱的要求上，对至少50%的图满足2＜αˆ＜3；4. 最强：最少90%的图形满足“强”的要求，至少95%的图形满足“超弱”的要求。
同时还有不属于上述任何类别的网络：1. 非无标度：既不是超弱也不是最弱的网络。
下图展示了上面叙述的无标度划分：
缩放参数在整个语料库中，中值估计缩放参数的分布参数αˆ集中在αˆ=2上，但有长的右尾，因此有32%的数据集αˆ≧3。从下图可以看出，α∈(2, 3)的范围是包括无标度网络特征最具代表性的范围。
在无标度结构的五类中，中位数αˆ的分布差异很大，对于属于“超弱”类别的网络，分布的广度与总体分布相似，右尾长且许多网络αˆ≧3，表明他们并不是特别合理的无标度网络。在“最弱”和“弱”的无标度中，中位数αˆ仍分布广泛，但是到“强”和“最强”的类别中，基本集中于αˆ∈(2, 3)。
可替代分布本文通过似然比测试对幂律分布和四种可替换分布进行了分析，分析结果如下表所示。
对指数分布来说，它具有较弱的尾部和相对较低的方差，相比于幂律分布33%的支持率，它有41%的支持率，这样的结果符合缩放参数的广泛分布，因为当α≧3时，度分布必须有相对较细的尾巴。正态对数分布是一个分布较宽且重尾的分布，但仍不是无标度的。表中显示它自身的支持率（48%）是幂律分布（12%）的三倍以上，也具有非常大的不确定性（40%）。
换句话说，其实正态对数分布至少与绝大多数度分布（88%）的幂律拟合的非常好，这表明许多先前确定的无标度网络实际上很可能是正态对数分布。威布尔或者说拉伸指数分布可以产生重尾或细尾分布，情况类似于指数分布。最后一个指数截止的幂律分布的结果显示大多数网络（56%）都倾向于使用具有截止模型的幂律，这表明有限尺度的影响是非常常见的。
评估无标度假设
给定拟合、测试和比较网络上幂律分布的结果，我们现在根据上述六个类别对每个类别进行分类。从下图可以看出有49%的网络不是无标度网络，有46%属于超弱的类别，而只有10%和4%的网络数据集可以被归为强和超强的类别中。这个实验结果表明真正的无标度结构可能并不如以往工作中所建议的普遍，且无标度结构可能并非实验中一个通用的模型。当然，这些数据也会随着各个不同领域的数据发生变化，具体结果如下图所示。
本文主要分析的重点是生物学、社会和科技三个具体领域的网络上。在生物网络中，有63%不属于无标度的类别，这一类别中真菌网络占了非常大的一部分，还包括一些蛋白质相互作用网络和一些食物网络等。在剩下来的网络中，有6%表现出最强，这部分主要是代谢网络。相比之下，社交网络呈现出不同现象，它竟然没有强和最强的类别，因此，社交网络充其量只能是微弱的无标度。
技术网络中有90%展现出超弱的性质，而且有28%属于强的类别。
稳健性分析为评估这些结果对评估方案本身的依赖性，我们进行了一系列稳健性测试。这些测试主要包括：（i）仅考虑简单数据集（无权、无向、无重边、单链）；（ii）我们从可替代的分布中删除截止的幂律分布；（iii）我们降低所有类别的百分比阈值，以便任何一个组成简单图满足要求的情况下都能包含在内；（iv）分析度分布的第一和第二距比率的缩放行为。
其中第三个测试结果如下图所示：由图可知，在考虑了“最松散”的参数化之后，降低每个类别的阈值，在此修改下，强和最强都为18%，这些测试结果表明，在主要评估方案的类别定义中使用的百分比要求不是过于严格，并且我们的结论对评估所使用的阈值的变化是可靠的。
第四个检测提供了对无标度假设的关键预测的模型独立性评估，由于矩<k^m>在m＜α-1上是有限的，且所有高阶矩都是逐渐发散的，因此在α∈(2, 3)的范围上，力矩比<k^2>/<k>^2随着网络规模n的增加而发散。从图中可以看出，跨网络、域和规模的比率之间存在着巨大的差异。例如10^2≦n≦10^3上的比率常常比网络大几个数量级。
讨论
本文对无标度假设的评估中使用了统计和分类思想来提供一种定量且严格的划分方法，从而评估某些网络中显示无标度结构的程度。通过评估来自各个领域的近1000个现实世界网络的度分布，我们发现无标度网络并非无处不在的，只有少于36个网络（大约4%）显示出无标度结构的超强性质，而在88%的网络中，对数正态拟合度分布甚至优于幂律分布。
在不同的领域中，无标度结构所占比例通常是不同的，这些差异为无标度结构真正可能会出现的地方提供了提示信息。相比之下，我们发现社交网络充其量是弱无标度的，尽管幂律分布是这些网络在统计上合理的模型，但却不是最好的模型。同时，本文的统计评估仅考虑网络的度分布，而对控制任何特定网络形式的其他结构模型或基础过程的描述相对较少。
本文揭示的现实网络的结构多样性既是难题也是机遇，以往工作中对解释和利用无标度模型的广泛关注表明对于产生非无标度结构模式的机制的了解相对较少，那么开发和验证用于在网络中生成更现实的网络结构的新颖机制就成为了未来主要的工作方向。