计算机科学

不变网络d'échelle

在具有许多松散连接的节点和许多超节点的情况下,尺度不变网络比随机网络更能抵抗多个节点的意外关闭。相反,几个超级节点的针对性攻击威胁了整个系统。

Albert-LászlóBarabási和ÉricBonabeau 科学档案N°66
本文仅供《 对于科学》的订户使用

网络无处不在!大脑是由轴突连接的神经细胞网络。细胞本身就是通过生化反应连接的分子网络。社团是另一种类型的网络,由由亲密,家庭或专业纽带团结在一起的个人组成。更大范围内,食物链和生态系统由物种网络组成。技术还提供其网络份额,主要是Internet。

如果网络无所不在,它们的结构和性质仍然是要研究的对象。复杂的遗传网络的多个失效节点之间的相互作用如何导致癌症?为什么计算机网络中的传染媒介传播如此之快?在某些网络的大多数节点停止服务后,为什么它们仍然可以正常工作?

最近,我们看到了回答这些问题的开始。我们发现,许多网络(从Internet到细胞新陈代谢,包括好莱坞演员的新陈代谢)都有共同的特征,包括少数节点具有大量链接而很少节点的事实。连接的。因此,网络的每个“站点”要么是一个相当隔离的节点(连接不紧密),要么是“超级节点”:没有节点可以代表整个节点。这样的网络都具有被称为“尺度不变性”的特性,它们表现出可预测的行为:例如,它们对意外故障具有显着的抵抗力,但极易受到协同攻击的影响。

这些网络由几个超级节点主导,这一概念证明了许多复杂的系统具有精确的架构,并受基本定律的约束,这些定律同样适用于单元,计算机,语言和社会的功能。而且,这些组织原则还将具有其他用途,例如保护Internet网络免受盗版或在其他方面与流行病作斗争。

占主导地位的节点

40多年来,在匈牙利数学家保罗·埃尔多斯(PaulErdös)和他的同事阿尔弗雷德·雷尼(AlfredRényi)两种先驱的工作之后,科学将复杂网络视为具有随机分支的图。通信网络和生物网络由随机连接的节点建模。他们方法的简单性以及他们一些结果的优雅,导致了一个新的研究领域的出现:随机网络。

根据随机网络理论的一种预测,如果将链接随机放置,则生成的系统是民主的:大多数节点具有大约相同数量的链接。实际上,在随机网络中,根据给定数量的链接表示节点的数学函数(即链接的分布)呈钟形:这是泊松分布。一方面,这意味着大多数节点具有接近平均值的许多链接,另一方面,几乎没有任何节点具有很少的链接或很多链接连接。

1998年,在我们的同事Hawoong Jeong和RékaAlbert的帮助下,我们决定绘制Internet网络图,并且我们相信我们会确定一个随机网络。的确,互联网用户只有在决定将其Web文档链接到哪个站点时才满足他们的个人利益,并且每个用户的利益随他们可以选择的页面数而变化,我们认为连接图是哪一个?结果是随机的。我们的测量结果并未证实这一预测。

我们构建了一个程序,该程序可以从一个网页跳转到另一个网页,并记录所有可能的链接。尽管这个虚拟机器人只访问了Web的一小部分,但他建立的地图显示,Web的凝聚力是由几个非常“连接”的页面来确保的。在我们的示例中,超过80%的页面具有少于四个链接,但是一小部分(少于所有节点的0.01%)具有超过1,000个链接。后来的研究甚至发现一个文档被超过200万个页面引用,也就是说,有200万个网页通过超链接引导到那里!

力量而不是鱼

通过计算具有k个链接的页面数,我们发现分布遵循非泊松定律,但遵循幂定律:一个节点连接到k个其他节点的概率与1 / k成正比n,其中,对于入站链接,n大约等于2。因此,任何节点只有另一个节点的入站链接的一半的可能性是四倍。

幂定律与表征随机网络的泊松分布有很大不同:幂定律不出现峰值,而是单调且递减的曲线。在对数坐标系中,这样的幂律由一条直线表示(请参见下图)。

与在随机网络中观察到的链接的民主分布不同,权力定律适用于一些超节点与几乎所有其他超节点链接并主导交换的网络:例如,谷歌就是这种情况。在某些网络中,每个节点的链接数不遵循泊松分布,因为某些超级节点具有巨大的链接数。这就是为什么我们将这些尺度不变网络命名为(系统没有特征尺度)的原因。

从那时起,计算机科学家就发现了许多系统中的尺度不变结构。在研究Internet网络时,我们查看了由超链接连接的页面的虚拟网络。 Riverside大学的Michalis Faloutsos,多伦多大学的Petros Faloutsos和卡耐基梅隆大学的Christos Faloutsos研究了Internet的物理结构。他们都探索了通过通信线路连接的路由器(连接计算机网络的设备和信息通过的设备),并表明该网络的拓扑结构也是规模不变的。

一些社会系统也是规模不变的。一个美国团队和一个瑞典团队表明,瑞典的性关系网络遵循幂律法:虽然大多数人一生中只有少数性伴侣,但有些(超节点)却拥有。数百。

德国基尔大学的Stefan Bornholdt进行的一项研究发现,通过电子邮件联系的人员网络也是规模不变的。科学家之间的协作网络(Erdös与近500位合著者撰写了1,400篇文章,他本人是数学界最大的超级节点之一)或数学界的某些网络也是如此。商业世界。甚至好莱坞演员网络也是规模不变的:大多数演员之间的联系很少,但每个都有数千个联系。

平等的结

研究网络的人越多,发现尺度不变结构的人就越多,这引发了一个重要的问题:像小区和互联网这样不同的系统如何具有相同的体系结构并遵循相同的规律?这些不仅具有各种性质的网络在规模上是不变的,而且它们具有显着的特性:由于某种未知数,我们对k项中n的值感到未知。n 幂律的取值通常在2到3之间。

一个问题仍然悬而未决:为什么随机网络理论不考虑超节点的存在?对Erdös和Rényi随机网络模型的检验给出了两个原因。两位数学家以为所有节点在放置链接之前都是已知的。相反,在Internet上,文档数量在不断增加:2000年,网站数量达到100万;他们是今天的200倍。大多数网络都经历了类似的扩张:例如,1890年好莱坞只有少数演员。今天,有超过半百万的人,新手与退伍军人建立了新的联系。同样,三十年前,Internet使用了一些路由器,但它仍在继续使用它们,现在有数以百万计的路由器,新的路由器连接到已经属于网络的路由器。最旧的节点总是更有可能获取新链接。

不是所有节点都相等。有数十亿种方法可以连接您的网页,但是大多数用户只了解网络的一小部分,并且该子集倾向于包含连接最多的网站,原因很简单,是最有名的。通过链接到这些节点,Internet用户通过称为“优先附件”的过程来增加他们的权重。

这两种机制-增长和优先依附-解释了超级节点的存在:创建新节点时,它们最好连接到连接更好的站点,与没有连接的邻居相比,它们最终获得更多的链接(请参阅第54页上的图)。这种机制通常适用于较旧的节点,因此较有可能成为超级节点。对于R. Albert,我们使用了数值模拟和计算方法来显示具有优先附件的扩展网络变得规模不变,并根据幂定律给出了节点的分布。这个简单的理论模型验证了我们对自然界中尺度不变网络的普遍性的解释。

增长和优先依恋甚至可能有助于解释生物系统中规模不变网络的存在。例如,新墨西哥大学的安德里亚斯·瓦格纳(Andreas Wagner)和英格兰牛津布鲁克斯大学的戴维·费尔(David Fell)表明,大肠杆菌细菌代谢网络中连接最紧密的分子具有较长的进化史!

随着人类活动越来越依赖于能源分配网络和通讯“网络”,人们普遍担心:这些类型的网络的可靠性如何?好消息是,复杂的系统出奇地抵抗了意外故障。这种鲁棒性来自何处?可以感觉到,网络中大量节点的停用导致其碎片化。随机网络的情况确实如此:如果消除了许多节点,则这些网络将被划分为许多小的孤立岛。

规模不变网络的致命弱点

对于规模不变的网络,情况有所不同:即使80%的随机选择的Internet路由器停止运行,其余20%的设备仍将继续提供连接且正常运行的网络(随机可以两两相连)。

规模不变网络的这种鲁棒性被固定在它们的拓扑中。节点的随机删除尤其会干扰小节点,因为它们比超级节点要多得多:消除连接不紧密的小节点不会显着干扰网络的拓扑。但是,网络仅依赖于几个“重要”超节点这一事实具有严重的缺陷:如果攻击是针对性的,则网络将非常脆弱。

我们已经表明,关闭某些Internet的主要超级节点会将系统拆分为无希望的隔离路由器的微型群集。超级节点对于网络的运行至关重要。少数知识渊博的黑客通过攻击其超级节点来破坏通信网络的可能性是真正的威胁。规模不变网络的致命弱点提出了一个重要的问题:多少个超节点对于整个网络的正常运行必不可少?

最近的研究表明,一般而言,删除少于5%到15%的所有超节点会导致系统崩溃。关于Web,我们已经表明,仅删除几个超级节点的定向攻击会严重破坏网络。因此,保护​​这些超级节点是避免因网络攻击而造成的大规模破坏的最有效方法。

我们对规模不变网络的了解有助于我们理解计算机病毒的传播,还可以理解疾病甚至模式的传播。流行病学家和市场分析师研究了数十年的扩散和渗透理论,预测了在特定人群中流行病传播的关键阈值的存在:传染性低于临界阈值最终消失。超过临界阈值,病毒呈指数级增长,感染整个人群。

巴塞罗那理工大学的Romualdo Pastor-Satorras和的里雅斯特理论物理中心的Allessandro Vespigniani建立了一个令人不安的结果:在尺度不变网络中,阈值为零。因此,所有病毒,甚至不是传染性很强的病毒都在人群中传播并持续存在。由于超级节点连接到大量节点,因此其中至少一个有被感染节点感染的风险。当这个超级节点受到感染时,它会感染许多其他站点,并危及其他超级节点,最终导致病毒在整个网络中传播。

应当指出,在商业和市场领域中,目标更多是引发流行病而不是遏制流行病。例如,“具有传染性”的促销活动试图以超级节点为目标,以加快产品的分销速度。规模不变网络上的工作提供了探索和利用这一现象的数学工具。

其他类型的网络

尽管规模不变网络无处不在,但有许多值得注意的例外。例如,美国的高速公路系统或能量分配系统不是规模不变的。对于材料物理学中已知的大多数网络而言,情况也并非如此:因此,在晶体的网格中,原子均具有与相邻原子相同数量的链接。

网络的全局拓扑并不是决定其行为的唯一参数,并且会干预各种参数:添加到给定节点的任何新链接有时都会带来高昂的代价,从而阻止了某些网络(例如美国的高速公路网络)。 )成为尺度不变式。对于社交网络,同一个家庭成员之间的链接比这些人及其关系之间的链接要牢固得多:疾病和信息通过这些链接更有效地传播。对于运输和通信系统,某些连接的拥塞是一个主要的困难:沿着特定链接的流量过多会使其无法使用,从而威胁到必须吸收过载的其他链接。

我们主要研究了复杂的系统,而忽略了它们的节点和链接的细节。通过使自己远离这些特性,我们澄清了支配这些看似难以理解的系统的组织原则,并且许多简单的假设已经重新制定。而且,在规模不变网络上获得的知识将使我们尤其能够从静态研究(拓扑)转向其动力学研究。

订阅并访问超过20年的档案!

订阅优惠

12期+ 4期特刊
纸质+数字版

+无限访问超过20年的档案

我订阅

订阅并访问超过20年的档案!

订阅优惠

12期+ 4期特刊
纸质+数字版

+无限访问超过20年的档案

我订阅

我们的最新出版物

回到顶部

已经有帐号了?

身份证明

标识自己可以访问您的内容

看到

还没有帐户 ?

注册

注册以激活您的订阅或订单问题。

创建我的账户