在网络理论中,无尺度网络(或称无标度网络)是带有一类特性的复杂网络,其典型特征是在网络中的大部分节点只和很少节点连接,而有极少的节点与非常多的节点连接。这种关键的节点(称为“枢纽”或“集散节点”)的存在使得无尺度网络对意外故障有强大的承受能力,但面对协同性攻击时则显得脆弱。现实中的许多网络都带有无尺度的特性,例如因特网、金融系统网络、社会人际网络等等。
源起
无尺度网络的概念是随着对复杂网络的研究而出现的。“网络”其实就是数学中图论研究的图,由一群顶点以及它们之间所连的边构成。在网络理论中则换一套说法,用“节点”代替“顶点”,用“连结”代替“边”。复杂网络的概念,是用来描述由大量节点以及这些节点之间错综复杂的联系所构成的网络。这样的网络会出现简单网络中没有的特殊拓扑特性。
自二十世纪60年代开始,对复杂网络的研究主要集中在随机网络上。随机网络,又称随机图,是指通过随机过程制造出的复杂网络。最典型的随机网络是保罗·埃尔德什和阿尔弗雷德·雷尼提出的ER模型。ER模型是基于一种“自然”的构造方法:假设有{\displaystyle n}个节点,并假设每对节点之间相连的可能性都是常数{\displaystyle 0\u003cp\u003c1}。这样构造出的网络就是ER模型网络。科学家们最初使用这种模型来解释现实生活中的网络。
ER模型随机网络有一个重要特性,就是虽然节点之间的连接是随机形成的,但最后产生的网络的度分布是高度平等的。度分布是指节点的度的分布情况。在网络中,每个节点都与另外某些节点相连,这种连接的数目叫做这个节点的度。在网络中随机抽取一个节点,它的度是多少呢?这个概率分布就称为节点的度分布。
在一般的随机网络(如ER模型)中,大部分的节点的度都集中在某个特殊值附近,成钟形的泊松分布规律。偏离这个特定值的概率呈指数性下降,远大于或远小于这个值的可能都是微乎其微的,就如一座城市中成年居民的身高大致的分布一样。然而在1998年,Albert-László Barabási、Réka Albert等人合作进行一项描绘万维网的研究时,发现通过超链接与网页、文件所构成的万维网网络并不是如一般的随机网络一样,有着均匀的度分布。他们发现,万维网是由少数高连接性的页面串联起来的。绝大多数(超过80%)的网页只有不超过4个超链接,但极少数页面(不到总页面数的万分之一)却拥有极多的链接,超过1000个,有一份文件甚至与超过200万个其他页面相连。与居民身高的例子作类比的话,就是说大多数的节点都是“矮个子”,而却又有极少数的身高百丈的“巨人”。Barabási等人将其称为“无尺度”网络。
定义
按生长方式定义:如果网络的每个节点的连接数与此节点产生新连接的概率成增函数关系,这个网络就叫无尺度网络。
按分布定义:如果网络中有一定数量的连接的节点数与此连接数量成减函数,这个网络就叫无尺度网络。
人造的网络结构大多是规则的。在随机的网络结构中,节点与其他节点的连结的数量呈正态分布;在规则的网络结构中,节点与其他节点的连结数量是固定的。以上两类网络中,节点与其他节点的连结的数量分布都有规则可循,因此是有尺度的网络。然而,用数学方法描绘互联网时,出乎意料地发现有些节点与大量的其他节点连结,形成一个个集散中心(称为集散节点),因而把互联网这样的网络称为无尺度网络(scale-free network)。
无尺度网络中包含无数节点,大部分节点与其他节点只有几个连结,有些节点与大量的其他节点连结,称为集散节点。无尺度网络不存在代表性的节点,但受少数集散节点的支配,并具有如下可预期的行为特性:对意外事件具有惊人的承受力,对协同式攻击很脆弱,受制于某些基本的法则。
特性
无尺度网络的特性,在于其度分布没有一个特定的平均值指标,即大多数节点的度在此附近。在研究这个网络的度分布时,Barabási等人发现其遵守幂律分布(也称为帕累托分布),也就是说,随机抽取一个节点,它的度d是自然数k的概率:
也就是说d=k的概率正比于k的某个幂次(一般是负的,记为 − γ)。因此k越大,d=k的概率就越低。然而这个概率随k增大而下降的“速度”是比较缓慢的:在一般的随机网络中,下降的速度是指数性的,而在无尺度网络中只是以多项式类的速度下降。
在现实中许多大规模的无尺度网络中,度分布的γ值介于2与3之间。在对数坐标系中,度分布将会是一条斜率介于-2至-3之间的直线。如左下图中,横坐标为节点的度,从10一直到10;纵坐标为找到这样的节点的概率从10 一直到10。最高度数的节点有882条连接。所有的蓝点大致成一条直线分布(绿色的直线)。