随机网络上全局级联的简单模型外文翻译资料

英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料

随机网络上全局级联的简单模型

Duncan J. Watts

哥伦比亚大学社会学系，纽约，10027

由Murray Gell Mann，圣菲研究所，圣菲，2002年2月14日，（收到审查2001年5月29日）

摘要

由小的初始触发的大而罕见的级联的起源冲击是一种表现为文化多样的现象时尚潮流，集体行动，规范和创新的传播，以及
基础设施和组织网络中的级联故障。这个论文提出了这一现象的可能解释一个稀疏、随机的互动代理网络的决策是由他们的相邻节点根据一个简单行为决定的阈值规则。确定网络的两个方案易于使用非常大的级联-这里称为全局级联-这很少发生。当级联传播受到限制时网络的连通性，级联大小的幂律分布被观察到，类似于标准中的簇大小分布渗透理论和自组织危机中的雪崩。 但当网络高度连接时，级联传播受到限制是通过节点本身的本地稳定性和大小瀑布的分布是双峰，意味着更极端的不稳定性所以难以预料。在网络邻居的分布高度偏差的第一个方案中，发现最连接的节点比平均节点更有可能触发级联，而不是在第二种状态。

最后，表明异质性在确定系统的稳定性方面起着不明确的作用：日益异质的阈值使系统更容易受到全球级联的影响; 但越来越多的程度分布使其不太脆弱。

小型的初始冲击如何能够级联以影响或破坏在过去相似的扰动中证实稳定的大型系统？ 为什么一些书籍，电影和专辑从晦涩，小营销预算中脱颖而出，成为流行的命中（1），当许多先天难以区分的努力不能超越噪音？为什么股市出现偶然的大幅波动，不能追溯到任何相应重要的信息的到来（2）？如果没有集中控制或公共沟通，大型基层社会运动如何开始？

这些现象都是经济学家称之为信息级联的例子（参考文献4;但这里称之为简单的级联），在此期间，人群中的个体表现出类似群体的行为，因为它们是基于其他人的行为，而不是依靠自己关于这个问题的信息。虽然它们是由完全不同的机制产生的，社会和经济系统中的级联（3-6）类似于物理基础设施网络（7,8）和复杂组织（9）中的级联故障，因为初始故障增加了后续故障的可能性 ，导致最终的结果，像1996年8月10日在美国西部输电网格（8）的级联故障，是非常难以预测的，即使各个组件的性质被很好地理解。他们自己的是，在连续的小故障和冲击存在的情况下，同样的系统常常表现出很大的稳定性，至少与最终产生级联的冲击一样大。因此，级联可以被视为许多复杂系统的强大但脆弱性质的具体表现（10）：一个系统可能长时间稳定，并经受许多外部冲击（强壮），然后突然显然莫名地展现出一个大的级联（脆弱）。虽然负责级联发生的社会，经济和物理机制是复杂的，并且在同一系统中，甚至在特定级联之间也可能有很大差异，本文提出了级联的一些一般特征可以用术语解释 的网络连通性，通过这些网络在个人之间传播影响力。 具体来说，本文讨论了一组定性观察，即（i）全局（即非常大的）级联可以由相对于系统大小非常小的外部事件（冲击）触发，（ii）全局级联发生很少相对系统收到的冲击的数量，可能由与之前的冲击无法区分的冲击触发。 模型动机：具有外部性的二元决策
这种模式的动机是考虑到个人人数，每个人都必须在两种替代行动之间作出决定，其决定明确地取决于其他成员的行为。在社会和经济制度中，决策者经常互相关注，因为它们对于问题本身的信息有限，甚至有限的处理即使是可用的信息的能力有限（6）。在决定要访问哪部电影（11）或餐厅（12）的时候，我们经常没有什么资料来评估替代品，所以我们经常依靠朋友的推荐，或者只是选择大多数人去的电影或餐厅。即使我们能够获得丰富的信息，例如当我们评估新技术，风险金融资产或候选人时，我们往往缺乏理解的能力;因此，我们再次依靠信任的朋友，同事或顾问的建议。在其他决策方案，如集体行动问题（3）或社会困境（13）中，个人的收益是他人行为的明确功能。而在另外一些问题上，涉及到传播新技术（14），例如一台传真机的附加单元的效用可能取决于已经出售的单位数量。因此，在所有这些问题上，无论细节如何，个别决策者有激励注意别人的决定。从经济学角度来说，整个类别的问题通常被称为具有外部性的二元决策（6）。 像简单化一样，二进制决策框架与令人惊讶的复杂问题相关。 举个例子，建立一个政治联盟或一个国际条约毫无疑问是一个复杂多方面的进程，有许多潜在的结果。 但是，一旦联盟存在或条约草案起草，决定是否必须加入二进制。 类似的推理适用于公司在两种技术之间的选择，或个人在两个邻里餐馆之间的选择 - 决策中涉及的因素可能很多，但决策本身可以被视为二进制。涉及二元决策问题的详细机制以及外部因素的起源在具体问题上可能有很大差异。 然而，在经济学和社会学文献中已经有许多应用，例如时尚（1,4,5），骚乱（15），犯罪（16），竞争技术（14）和创新的传播（17 ，18），公约（6）和合作（13） - 决策本身可以被认为是一个功能，只是其他代理人的相对数量，被观察选择一个替代方案（6）。 由于许多决策本身是昂贵的，需要承担时间或资源，所以相关决策功能经常表现出很强的门槛特征：代理人在切换状态下显示惯性，但一旦达到个人门槛，即使是单个邻居的动作也可以将其从一个状态提升到另一个状态。

型号规格
具有捕获上述基本特征的外部性的特别简单的二进制决策规则如下：个体代理人观察k个其他代理的当前状态（0或1），我们称之为其邻居，并采用状态1，如果至少一个阈值分数Phi;其k个邻居处于状态1，否则采用状态0。

为了解决决策者群体中的知识，偏好和观察能力的变化，个体阈值以及邻居数k都可以是异构的。首先，每个代理被分配一个阈值Phi;从单位间隔定义的分布f（Phi;）中随机绘制并归一化，使得，但否则是任意的。接下来，我们构建一个n个代理的网络，其中每个代理与概率为的k个邻居连接，并且邻居的平均数为。虽然我们会继续说一个代理人的邻居，但我们应该将它们简单地看成是与手头问题有关的一组信号。更正式地，我们说代理在图中由顶点（或节点）表示;相邻顶点通过边连接；是图的度数分布; z是平均度（在物理学中，z通常称为协调数）。为了模拟级联的动力学，人口最初是全部的（状态0），并且在时间t=0被个开启的顶点（状态1）扰乱。然后，人口随着所有顶点按照上述阈值规则的随机异步顺序更新其状态，在连续的时间步长演化。一旦顶点打开，它将在动态持续时间内保持打开（活动状态）。

在社会科学文献中，这种决策规则通常来源于非合作游戏的收益结构，如囚徒困境（3,6）或随机抽样程序（18）。但是，当更广泛地被认为是国家的变化 - 而不仅仅是一个决定 - 该模型属于更大类的传染性问题，包括输电网络（8）或互联网（19,20）等工程系统的故障模型， ，流行病学（21）和渗透（22,23）疾病传播模型，以及多种细胞自动机模型，包括随机场Ising模型（24），自举渗透（25,26），多数投票（27,28） 扩散激活（29）和自组织关键性（8,29）。

然而，该模型在某些重要方面与其他传染性模型不同。 （i）与流行病学模型不同，个体之间的传染性事件是独立的，阈值规则有效地引入了局部依赖性;也就是说，单个感染的邻居对给定节点的影响在很大程度上取决于节点的其他邻居的状态。 （ii）与引导渗透和自组织关键性模型（其也表现出局部依赖性）不同，阈值不是以选择给定替代方案的节点的邻居的绝对数，而是邻域的相应分数来表示。这是施加决策问题的自然条件，因为决策者收到的信号越多，任何一个信号变得越小。 （iii）与通常以常规格子建模的随机场Ising和多数投票模型不同，这里我们关注异构网络;也就是说，个人具有不同数量的邻居的网络。所有这些特征 - 局部依赖性，分数阈值和异质性 - 对于级联的动力学是至关重要的。此外，虽然它们与阈值条件明显相关，但网络异质性和阈值异质性不相等，因此需要单独考虑。

任意随机图上的精确解
本文的主要目的是探讨互联系统对全球级联的脆弱性是如何依赖于人际关系网络来管理个人对世界的信息，并因此决定他们的决定。因为建立关系和收集信息是昂贵的练习，互动和影响网络往往非常稀疏（17）-一般来说，真实网络似乎是真实的特征（30）-我们只考虑具有z的网络的属性。在没有任何已知的问题几何的情况下，稀疏交互网络的自然选择是一个无向随机图（31），具有n个顶点和指定的度分布。虽然随机图不被认为是大多数现实世界网络的高度现实的模型（30），但由于它们的相对易行性，它们通常被用作第一近似值（19,20,32），并且这里遵循传统。我们的方法集中在两个数量上：（i）全局级联将由单个节点（或节点的小种子）进行绑定的概率，其中我们将全局级联正式定义为占用无限网络有限部分的级联;和（ii）一旦触发全球级联的预期大小。当描述我们的结果时，术语级联因此是指由初始种子触发的任何大小的事件，而全局级联保留用于足够大的级联（实际上，这意味着超过大而有限网络的固定分数）。

在任何足够大的随机图中，（其中c是一些常数）和（即与一个小的初始种子稀疏连接），我们可以假设小种子的局部邻域不会包含任何短周期；因此，与初始种子相邻的顶点不会与多于一个种子成员相邻。在无限网络的情况下，有限的z或由单个顶点组成的种子，这种近似变得精确。在这种情况下，种子可以生长的唯一方法是，如果至少有一个直立邻居有一个阈值，或等效地具有度。我们称这种一步感觉不稳定的顶点，脆弱的和不稳定的顶点，注意到仅当所述种子很小时，该区别才适用。（数值模拟表明，比三个数量级的种子小于系统尺寸足够小）。大型种子的情况将在后面讨论。

虽然脆弱性条件相当普遍，但由于具体性，我们使用创新传播的语言（17），其中初始种子起着创新者的作用，而脆弱顶点对应于早期采用者。除非创新者与早期采纳者的社区有联系，否则不可能有级联。事实上，如下所示，创新的成败可能取决于创新者本身的数量和特征，而不是早期采用者社区的结构。显然，网络中存在的早期采用者越多，创新就越有可能传播。但是，其增长的程度，从而影响整个网络的敏感度，这不仅取决于早期采用者的数量，而且取决于它们之间的相互关系，也取决于更大的社区，包括早期和晚期多数，谁不倾向于直接对创新者作出反应，但如果暴露于多个早期采用者，谁可以间接影响。在这个模型的上下文中，我们推测，全局级联的所需条件是易受攻击的顶点的子网络必须在整个网络中渗透（22），这就是说，最大的连接的易受攻击的集群必须占用一个无限网络的有限部分。不管整个网络如何连接，这里的说法是，只有最大的易受攻击的群集渗透是全球级联可能的。

这个条件，我们称之为级联条件（见下面的等式5）具有将复杂动力学问题减少到可以使用生成函数方法解决的静态渗透问题的相当大的优点。 类似的技术已被用于其他地方（20,32）来研究随机图的连通性; 这里的基本方法被修改（参考文献32中详细描述），以集中于易受攻击的顶点。 通过构造，每个顶点具有概率的度数k，并且在上述的脆弱性条件下，具有k度的顶点易受概率的影响。 因此，具有度k并且易受攻击的顶点u的概率为，并且脆弱顶点度的相应生成函数为：

[1a]

当 [1b]

和.通过整合度数分布和阈值分布中包含的所有信息，只生成脆弱顶点的度数分布的所有时刻，其中可以通过评估的导数来提取相关矩阵， 在x=1为了本文的目的，两个最重要的数量是（i）群体的脆弱部分和（ii）脆弱顶点的平均程度。 因为我们对级联从一个顶点到另一个顶点的传播感兴趣，所以我们还需要一个弱点顶点v的度数分布，它是我们最初选择的顶点u的随机邻居。 v的程度越大，越有可能成为你的邻居; 因此，选择v的概率与成比例，对应于u的邻居的正确归一化的生成函数为：

[2]

为了计算易受攻击的顶点集群（早期采用者的社区结构）的属性，我们引入了类似的生成函数

和，

其中qn是随机选择的顶点将属于大小为n的易受害群体的概率，rn是初始选择的顶点的邻居的相应概率。 我们通过跟随随机边缘到达的任何大小为n的有限簇可以被认为是由较小的这样的簇组成的，其累积大小必须等于n。 因为渗透下的足够大的随机图可以被看作是一个纯分支结构，所以我们可以忽略亚群落的周期连接的可能性，所以每一个亚群可以独立于其他亚群。 （以下将讨论渗透下的无限簇的存在）。因此，大小为n的有限簇的概率只是其（也是有限）子簇的概率的乘积。 从生成函数（20,32）的属性可以看出，H1（x）满足以下自相关性方程：

， [3a]

从中可以计算出

[3b]

这两个方程式3a和3b对应于所选择的顶点不易受到的概率，第二项考虑了附着到本身易受攻击的顶点的脆弱群集的大小分布。 因此，生成易受攻击群集大小分布的所有时刻，其中最重要的是针对我们当前的目标是平均易受攻击群集大小，因为这是在渗透时分歧的数量。 将上述和的表达式代入，我们发现

， [4]

当时发生偏差

[5]

方程5级联条件解释如下：当，网络中的所有易受攻击的群集都很小;因此，早期采用者彼此隔离，无法产生级联成为全球所必需的动力。但是当，脆弱集群的典型尺寸是无限大的，这意味着渗透脆弱集群的存在，

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[137200]，资料为PDF文档或Word文档，PDF文档可免费转换为Word