无标度网络

......更多详情>>

对于充分大的k，若存在一个正常数c，使得网络的度分布大于等于某个度指数τ的幂律，如 ，则该网络可以称为无标度网络。如果存在无穷多的度值概率为零，那么需用幂律分布的补分布 在阶梯下降的离散点来替代

在世纪之交，《自然》和《科学》杂志分别发表了两篇重要的网络文章。第一篇提出了小世界网络，另一篇提出了无标度网络。于是网络概念引起了国际学术界的广泛关注，文章如雨后春笋般地涌现。

网络科学的内容极其丰富。下面介绍我参与研究过的几类网络。

第一类是无标度网络。无标度网络是少数hub节点拥有大量的连线，而大部分节点却很少连线的异质性网络。Barabási和Albert在引入无标度网络概念时，认为现实世界的大部分网络都不像随机网络那样具有泊松度分布，而是度分布呈现幂律衰减的尾部。众所周知，泊松度分布的形状像一条钟形曲线，幂律衰减度分布在双对数坐标上，尾部近似一条直线。前者在钟形顶部对应位置处有一个特征标度，后者由于幂律函数对测量测度的改变拥有不变性，失去了特征标度。英文scale-free一词，即无标度准确地反映了这种不变性的涵义。

无标度网络的第一个数学模型是由Barabási等人提出的择优增长BA模型。给定一个初始网络，每步增加一个节点和m条连线，新增连线按度择优概率连接到现有节点。他们利用平均场方法推导出该模型网络的度分布密度具有幂律形式，。

Barabási等人推导BA模型网络度分布的平均场方法，不是很好理解。于是人们又分别提出了主方程方法和率方程方法。这些方法都是从物理角度出发的探索，缺乏严密的数学论证。我们根据BA模型网络生成规则的无记忆特性，分别用齐次马氏链 、非齐次马氏链 、向量马氏链，给出了上述三种方法的严格数学论证。其中平均场方法对应的齐次马氏链，需要用到泊松过程的稀疏化理论。

与网络有关的马氏链，我们称为网络马氏链，它在网络研究中有着重要的应用。

无标度网络的提出催生了网络科学，并促使其蓬勃发展。面对网络数据，如何判断它是否为无标度网络，人们往往看它的度频率在双对数坐标上是否呈一条直线。然而，即使一条拟合的很好的直线，它都可能不是幂律分布，甚至没有幂律尾部！

少数hub节点的存在，对无标度网络起着主导的作用，使得网络拓扑及其动力学特征涌现出前所未有的属性，人们称为无标度网络特性。通过模拟，与随机网络比较，无标度网络在网络的直径、巨分量、可控性等，面对蓄意攻击，hub节点都脆弱；而对节点的随机失效稳健。又当度指数小于等于3时，疾病容易在网络上传播等等，但这些结论都存有争议。以可控性为例，下面将介绍的自然数同余网络是无标度网络，但它的可控性面对蓄意攻击，hub节点稳健而不脆弱。因此有理由怀疑“稳健而又脆弱”是否为无标度网络的普适特性？除此之外，人们还发现，从幂律度分布网络随机抽样所得的子网络不再具有幂律度分布。这是一个颠覆性的命题，因为实际网络数据往往不会完整。甚至有人对无标度网络是稀疏网络都表示质疑。究其原因，这与无标度网络的定义和分类有关。

这里还涉及到有限无限的哲学命题。实际网络都是有限网络，模型网络才能无限增长。幂律理论来自无限系统，而现实系统都是有限的。因此谈论某个现象具有幂律，必须具备机制成熟并得到统计支持。可惜许多关于幂律的报告都缺乏机制成熟和很少统计支持。复杂现象的观察已发现幂律无所不在。除了Barabási律:无标度网络度分布渐近幂律;还有Pareto律：超过财富门槛的个体频数服从渐近幂律;Zipf律：单词频数与词频序号也遵循幂律；Heaps律：词汇量与总的词数遵循渐近次线性幂律等等。它们之间有何关系也是人们关心的问题，需要通过逻辑严密的清晰推理去回答。为此我们发表过系列文章讨论。

基于上述问题，根据我们在物理期刊上发表过的有关论文，我在2011年撰写了《网络度分布理论》一书，从理论上给出了部分的回答。2014年又在《国家科学评论》上撰文给出了无标度网络的严格定义和分类。

无标度网络是网络科学的一个重要概念。什么是无标度网络？关键看它的度分布：是幂律，还是幂律尾部，还是一般的重尾分布？根据Barabási及其合作者提出的几个代表性的网络模型，应该是比幂律衰减更慢的重尾分布才比较合理。因此，可以给出如下的定义：对于充分大的k，若存在一个正常数c，使得网络的度分布大于等于某个度指数τ的幂律，，则该网络可以称为无标度网络。如果存在无穷多的度值概率为零，那么需用幂律分布的补分布在阶梯下降的离散点来替代。因补分布也是幂律，不过这时无标度网络的度指数需要加1。

根据定义，可将无标度网络度分布，分解成一个k的正函数乘以幂律（当有无穷多的度值概率为零时，要用补分布去替代），则可根据正函数的形态对无标度网络给予分类如下：第一，如果这个正函数是一个常数，定义域是自然数，则度分布为精确的幂律分布；第二，如果正函数以一个正的常数为极限，这称为幂律尾部；第三，如果正函数没有极限，但存在两个正常数的范围里面，这称为幂律行为，它围绕着幂律始终上下摆动；第四，若正函数没有极限，但有正的下界，称为幂律关系，例如，阿波罗尼斯网络度分布就属于这一类。然而，具有指数截尾的幂律，这种网络按照定义就不应该说是无标度网络。显然上述四类无标度网络，都有后者包含前者的关系。在这样一个分类栏目下，有关的争议问题可望得到解决。