展开全部 +
首页 . 理学 . 系统科学 . 系统学 . 复杂网络系统 . 〔复杂网络基本概念〕 . 复杂网络拓扑理论模型

无标度网络

/scale-free network/
条目作者史定华

史定华

最后更新 2024-07-02
浏览 477
最后更新 2024-07-02
浏览 477
0 意见反馈 条目引用

少数中心节点拥有大量的连接,而大部分节点却很少连线的异质性网络。

英文名称
scale-free network
所属学科
系统科学

美国学者A.-L.巴拉巴斯R.阿尔伯特[注]在引入无标度网络概念时,认为现实世界的大部分网络都不像随机网络那样具有泊松度分布,而是具有幂律衰减度分布,即,其中表示网络中度值为的节点的比例,符号表示正比于的意思。泊松度分布的形状像一条钟形曲线,幂律衰减度分布在双对数坐标上尾部近似直线。前者在钟形顶部对应位置处有1个特征标度,后者由于幂律函数对测量尺度的改变拥有不变性,因此无标度(scale-free)一词准确地反映了这种不变性的涵义。

无标度网络是网络科学的一个重要概念。网络的度分布包括幂律,幂律尾部,重尾分布。根据巴拉巴斯及其合作者提出的多个代表性网络模型,应该采用比幂律衰减更慢的重尾分布。因此可给出如下数学表达形式:对充分大的,若存在正常数使得网络的度分布,其中为度指数,则称该网络为无标度网络。如果网络的幂律分布存在无穷多度值的概率为零,那么需用幂律分布的补分布替代。也是幂律,若指数为,这时无标度网络度指数

关于无标度网络的第一个数学模型是由巴拉巴斯等提出的择优增长BA模型。给定一个小的初始网络,每步增加1个节点和条连线,新增连线按度择优概率连接到现有节点,利用平均场方法推导出网络度分布。择优连线需要全局信息,在实际中较难实现,有一种替代办法是采用随机复制模型,即对新加入节点随机复制一个现有节点并以概率复制其部分连线,从而得到网络度分布。人们还根据实际网络背景提出了许多模型,例如阿波罗尼斯网络模型。

少数集散(hub)节点的存在,对无标度网络的运行起着主导的作用,使得网络拓扑及其动力学特征涌现出前所未有的属性,人们称为无标度特性。通过模拟,与随机网络比较,人们发现无标度网络在网络直径、巨分量、可控性等方面,对蓄意攻击集散节点脆弱而对节点的随机失效稳健。当时,疾病容易在网络上传播等结论,这些结论还存有争议。以可控性为例,自然数同余网络是无标度网络,但该网络对蓄意攻击集散节点稳健而不脆弱。因此对于“稳健而又脆弱”是否为无标度网络的普适特性还未有定论。

根据定义,可将无标度网络度分布分解成一个正函数乘幂律(当有无穷多度的值概率为零时,需用补分布替代),从而可根据正函数的形态对无标度网络度分布进行分类,具体分类如下:①若正函数为常数,定义域为自然数,则度分布为精确幂律分布。②若正函数以正常数为极限,则称为幂律尾部。③若正函数没有极限,但在两个正常数范围内,则称为幂律行为。它围绕幂律始终上下波动。④若正函数没有极限,只有正下界,则称为幂律关系。例如阿波罗尼斯网络度分布就属于这一类。

通过对复杂现象的观察,发现幂律广泛存在。除了巴拉巴斯律(无标度网络度分布渐近幂律)、还包括帕累托律(超过财富门槛的个体频数服从渐近幂律)、齐普夫律(从大到小排序的单词频数与词频序号遵循幂律)和希普斯律(词汇量与总词数遵循渐近次线性幂律)。它们之间有何关系是人们关心的问题,需要通过逻辑严密的清晰推理去回答。

无标度网络是异质性网络,全齐性网络是典型的同质性网络。全齐性网络指网络中各节点的度数d、路和l、周长g都相同的网络。这里路和定义为网络中其余节点到该点最短路径通过的连线数目之和;周长定义为从该点出发再返回该点最短路径通过的连线数目之和。以下为两个代表性的全齐性网络(图1、图2)。

图1 全齐性网络N=10;d=3,l=15,g=5图1 全齐性网络N=10;d=3,l=15,g=5

图2 全齐性网络N=18;d=3,l=41,g=6图2 全齐性网络N=18;d=3,l=41,g=6

探索这两个极端网络类的结构对功能的影响具有重要意义。

无标度网络的提出催生了网络科学并促使其蓬勃发展。面对网络数据,如何判断它是否为无标度网络,往往看它的度频率在双对数坐标上是否呈一条直线。然而,即使是一条拟合很好的直线,它都可能不是幂律分布,甚至没有幂律尾部。另外,度指数的确定也引发了极大争议,在阿波罗尼斯网络上表现尤为突出,原因是它有无穷多度的值概率为零。人们还发现,从幂律度分布网络随机抽样所得子网络不再具有幂律度分布。这是一个颠覆性的命题,因为所得实际网络数据往往不会完整。甚至有研究对无标度网络都是稀疏网络表示质疑。究其原因,这与无标度网络分类有关。

  • BARABÁSI A L, ALBERT R.Emergence of Scaling in Random Networks.Science,1999,286(5439):509-512.
  • SHI D.Critical Thinking of Scale-Free Networks: Similarities and Differences in Power-Law Random Graphs.National Science Review,2014,1(3):337-338.

相关条目

阅读历史

    意见反馈

    提 交

    感谢您的反馈

    我们会尽快处理您的反馈!
    您可以进入个人中心的反馈栏目查看反馈详情。
    谢谢!