具有任意度分布的随机图及其应用

1、具有任意度分布的随机图及其应用M.E.J. Newman, S.H. Strogatz, and D.J. Watts, Phys. Rev. E 64, （2001）.近来关于社交网络和互联网的结构的工作已经集中关注具有与在过去广泛研究的泊松度分布显着不同的顶点度的分布的图。在本文中，我们详细地开发具有任意度分布的随机图的理论。除了简单的无向，单向图，我们考查定向和二分图的属性。在其他结果中，我们得到精确表达式，其中巨分量首先形成的相变的位置，平均分量大小，巨分量的大小（如果有的话），距离随机选择的顶点一定距离的顶点的平均数量，以及图中顶点 - 顶点距离的平均。我们将我们的理论应用于一些真实

2、世界的图形，包括科学家和财富1000强公司董事的全球网络和协作图。我们证明，在某些情况下随机图与适当的顶点度分布预测是令人惊讶的准确性的现实世界的行为，而在其他人有一个可衡量的理论与现实之间的差异，可能表明网络中的额外的社会结构的存在不被随机图捕获。1、介绍。随机图1是点或顶点的集合，具有线或边，其随机连接它们的对图1(a)。随机图的研究有悠久的历史。从二十世纪五十年代和二十世纪六十年代Erdo和Renyi的有影响力的工作开始，随机图论已经发展成为现代离散数学的支柱之一，并产生了大量的结果，它们许多非常巧妙，描述了图形的统计特性，例如组件尺寸的分布，巨分量（giant component）的存

3、在和大小以及典型的顶点 - 顶点距离。在几乎所有这些研究中，已经假设两个顶点之间的边的存在或不存在与任何其它边的存在或不存在无关，使得每个边可以被认为以独立的概率p存在。如果在图中存在N个顶点，且每个顶点平均连接z条边，则显然p = z /（N-1）是很平常的，其对于大的N通常由z / N近似。连接到任何特定顶点的边的数量被称为该顶点的度k，并且具有由下式给出的概率分布pk其中第二等式在大N的极限中变得精确。这种分布我们认为是泊松分布：普通随机图顶点度具有泊松分布，这是一个关键点，正如我们现在解释的。随机图形不仅仅是一个数学玩具; 它们已广泛用作各种类型的现实世界网络的模型，特别是在流行病学中

4、。疾病通过社区的传播强烈依赖于感染该疾病的人和对其感染的人之间的接触模式。该模式可以描述为网络，其中个体由能够通过边传播疾病的顶点和接触表示。被称为易感/感染/恢复模型的大类流行病学模型5-7经常使用所谓的完全混合近似，这是假设接触是随机和不相关的，即它们形成随机图。然而，随机图表证明具有作为这种现实世界现象的模型的严重缺点。虽然很难通过实验确定疾病传播的联系网络的结构8，已经对其他社会网络进行了研究，例如各种社区内的友谊网络9-11，网络电话呼叫12,13，航空公司时间表14和电网15，以及物理或生物系统网络，包括神经网络15，聚合物的结构和构象空间16,17 ，代谢途径18,19和食物网2

5、0,21。发现13,14在许多这些网络中的顶点度的分布与泊松分布 - 通常是巨大的不同 - 可测量不同 - 这强烈暗示，如其他地方22所强调的，这样的网络，我们会错过，如果我们用普通（泊松）随机图来近似它们。（图1:（a）随机图的示意图，圆表示顶点，线表示边。（b）有向随机图，即其中每个边仅在一个方向上延伸的随机图。）另一个广泛研究的网络是互联网，其结构已经吸引了非常大量的细查，学术和其他方面，从1993年开始疾速上升到公众可见度。世界各地的网页可以被认为是一个图形和它们之间的超链接作为边。经验研究23-26已经表明，该图具有顶点度的分布，其是严重偏斜的并且具有指数在-2和-3之间的脂肪（幂律

6、）尾。（互联网的基础物理结构也具有这种类型的度分布）这种分布不同于泊松，因此我们预期简单的随机图给出网络的结构性质的非常差的近似。然而，网络在另一方面与随机图不同：它是定向的。网络上的链接从一个页面到另一个页面只在一个方向上引导参见图1(b)。如Broder等人26，这对一个页面从另一个页面的典型可访问性有重大的实际影响，这种效果也不会被简单的（无向）随机图模型捕获。已经吸引细查的另一类网络是协作网络类。这种网络的例子包括公司董事会28-31，公司共同所有权网络32，科学家33-37和电影演员15的合作。除了具有强非泊松度分布14,36，这些网络具有二分体结构;在图上存在两种不同类型的顶点，其

7、中链接仅在不同种类的顶点之间运行38，参见图2。例如，在电影演员的情况下，两种类型的顶点是电影和演员，并且网络可以表示为具有在每个电影和出现在其中的演员之间运行的边的图形。研究人员还考虑了这个图的投影到仅仅演员的单一空间，也称为单模网络38。在这样的投影中，两个演员被认为是连接的，如果他们一起出现在电影中。然而，单模式网络的构造涉及丢弃包含在原始二分网络中的一些信息，并且出于这个原因，更期望使用完全二分体结构来模型化协作网络。考虑到目前在这里描述的许多图的结构的高度关注39，并且给定它们与在过去研究的普通随机图的实质性差异，如果我们可以推广数学的随机图到非泊松度分布，以及定向和二分图。在本文中

8、，我们只是这样做，详细说明了每个这些图类型的统计属性如何可以精确计算在大图规模的限制下。我们还举例说明了我们的理论应用于一些真实世界网络的建模，包括www和协作图。（图2：二分图的示意图（左），例如电影和出现在其中的演员的图。在这个小图中，我们有四个电影，标记为1到4，和11个演员，标记为A到K，边将每个电影连接到演员的演员。在图片的右半部分，我们显示了11个演员的图形的单模式投影。）2、具有任意度分布的随机图。在本节中，我们开发了一种公式，用于计算各种数量，包括局部和全局的大型单向无向图，其顶点的度具有任意概率分布。在所有方面，除了它们的度分布之外，这些图被假定为完全随机的。这意味着所有顶点

9、的度是从指定分布绘制的独立的相同分布的随机整数。对于这些度的给定选择，也称为“度序列”，从具有该度序列的所有图的集合中随机均匀地选择图。在本文中计算的所有属性在以这种方式生成的图的集合上被平均。在大图规模的限制中，等价过程是仅研究一个特定度序列，在具有该序列的所有图上均匀地平均，其中选择该序列以尽可能接近期望的概率分布。后一个过程可以被认为是随机图的“微规则集合”，其中前者是一个“规范集合”。对任意度分布的随机图一些结果是已知的：在两个美丽的最近的论文40,41，Molloy和Reed已经得出了巨分量首次出现的相变位置的公式，以及巨分量的大小。（这些结果是在微规模集合内计算的，但同样适用于大系

10、统大小限制中的规范）。本文中提出的公式给出了这些结果的另一种推导，也提供了一个获得其他感兴趣的量的框架，其中一些我们计算。在第三和第四章中，我们将公式扩展到有向图（例如万维网）和二分图（例如协作图）的情况。A 生成函数。我们的方法基于生成函数42，对于我们的目的其中最根本的，是生成函数的顶点度k的概率分布。假设我们有一个不可分无向图 - 一个熟人网络，例如大的N，N个顶点。 我们定义其中pk是图上随机选择的顶点具有度k的概率。假设分布pk正确地归一化，因此对于这里考虑的所有生成函数也是如此，只有一些重要的例外，我们将在适当的点注释。因为概率分布是归一化的和正定的，对于所有|x|1也是绝对收敛的

11、，因此在该区域中没有奇点。本文的所有计算将局限于|x|1的区域。函数以及实际上任何概率生成函数具有许多属性将证明在后续开发中有用的。导数。概率pk由G0的第k阶导数给出因此一个函数概括包含离散概率分布的所有信息，我们说函数“生成”概率分布。矩。由生成函数生成的概率分布的平均值 - 例如，在的情况下的顶点的平均度z由下式给出：因此，如果我们可以计算生成函数，我们也可以计算它生成的概率分布的平均值。也可以从更高的导数计算更高的分布矩。一般来说，我们有幂。如果通过给定生成函数生成对象的属性k的分布，则通过该生成函数的m次幂生成对对象的m次独立实现之间总和为k的分布。例如，如果我们从大图中随机选择m个

12、顶点，则这些顶点的度的和的分布由生成。为了看到为什么会这样，考虑只有两个顶点的简单情况。单个顶点的生成函数的平方可以扩展为很清楚，该表达式中的幂的系数正好是所有乘积的和，使得j + k = n，因此正确地给出两个顶点的度的和为n的概率。简单地说服自己，这个属性也扩展到生成函数的所有更高的幂。所有这些属性将用于本文中给出的推导。对我们来说另一个重要的量是通过随机选择的边到达的顶点的度分布。这样的边以与该顶点的度成比例的概率到达顶点，因此顶点具有与kpk成比例的度的概率分布。正确归一化的分布由生成。如果我们从随机选择的顶点开始并沿着该顶点的每个边到达k个最近邻居，则到达的每个顶点具有由该函数剩余输

13、出边生成的分布，除以x的一次幂，以允许对于我们到达的边。因此，输出边的分布由函数生成其中z是平均顶点度，如前所述。这些输出边中的任何一个连接到我们开始的原始顶点或者其任何其他直接邻居的概率为，因此可以在大N的极限中被忽略。因此，利用上述生成函数的“幂”属性，用于原始顶点的第二邻居的数目的概率分布的生成函数可以被写为类似地，第三最近邻的分布由生成，等等。第二邻居的平均数是其中我们已经利用了事实：（可能有人试图推测，由于第一相邻的平均数是，等式（5），以及第二相邻的平均数是，方程（11），那么第m个邻居的平均数应该由在x = 1时评估的的第m个导数给出，然而，如第二章F所示，这个猜想是错误的。）B

14、 例子。为了使事情更具体，我们立即介绍一些具体图表的例子来说明如何进行这些计算。(a) Poisson分布图。这种类型的图形的最简单的例子是其中度分布是二项式的，或者是在大N极限中的泊松。这种分布产生了许多数学家研究的标准随机图，并在第一章中讨论。在该图中任何两个顶点之间的边的存在的概率p = z / N对于所有顶点是相同的，并且由其中最后的等式适用于极限N。然后平凡的表明顶点的平均度确实是，度的概率分布由给出，这是普通泊松分布。还要注意对于这种特殊情况，我们有，使得在一个顶点的输出边的分布是相同的，不管我们是通过随机选择一个顶点到达那里，或者随机选择边。这个属性是泊松分布随机图所特有的，这就

15、是为什么这种随机图的理论特别简单的原因。(b) 指数分布图。也许下一个最简单的类型图是顶点度具有指数分布的图其中是常数。此分布的生成函数是具有指数度分布的图的示例在第五章A中给出。(c) 幂律分布图。最近对www网络和社会网络的属性的兴趣导致我们调查顶点度具有幂律分布的图的属性。这样的图形已经讨论由Barabas与同事22,23和Aiello等人13。在本文中，我们将看到度分布由下式给出的图其中C，和是常数。包含指数截止的原因有两个：首先许多真实世界的图似乎显示出这个截止14,36; 第二，对所有它使得分布可归一化，而不只是2。常数C通过归一化的要求而固定，得到 ，于是其中是x的第n个多重对数

16、函数。对于那些不熟悉这个函数的人来说，它对于我们的目的的突出特征在于，对于所有n，在x = 0处是零并且在0x 时，巨分量存在。我们的生成函数形式仍然有效，当在图中有一个巨分量，但是由定义，然后生成的分量大小的概率分布除了巨分量。这意味着H0(1)不再是单位，因为它对于迄今为止考虑的其他生成函数，而是替换取值1-S，其中S是巨分量占据的图的分数。我们可以使用它来从等式（26）和（27）计算巨分量的大小，从而：其中是最小的非负实数解这个结果是由Molloy和Reed 41用不同的方法推导出来的。平均分量大小的正确的一般表达式，如果有一个，除去（形式无限）巨分量，是当不存在巨分量（S = 0，u

17、= 1）时，等价于等式（31）。例如，在具有泊松度分布的普通随机图中，我们有 式（12），因此我们简单地发现1-S = u是 u = G0（u）的一个解，或等效地平均分量大小由下式给出这些都是众所周知的结果1。对于具有纯幂律分布的图具有的等式(17)，S由等式（34）给出，其中u是最小的非负实数解对于所有的2，这给出u = 0，并且因此S = 1，这意味着随机选择的顶点属于巨分量的概率趋于1当。对于 2的图，属于巨分量的概率严格小于1，即使对于无穷大k。换句话说，2巨分量基本上填充整个图形，但 2不是。这些结果是由Aiello等人通过不同的方法得到的13。E 群集大小分布的渐近形式。关于生成函

18、数系数的渐进性质的各种结果是已知的，其中一些可以有用地应用于由生成的簇大小的分布。接近相变，我们期望分布的尾部表现为其中常数和可以从的性质计算如下。截止参数s*与生成函数的收敛半径| x * |简单地相关42,44，根据收敛半径|x*|等于最靠近原点的H0(x)中的奇异点的位置x*的大小。从等式（27），我们看到这样的奇点可以通过G0(x)中的单项或通过H1(x)中的单项而产生。然而，由于已知G0(x)中的第一奇点在单位圆外（Sec.IIA），并且当我们进入相变时，H1(x)中的第一奇点倾向于x = 1（见下文），因此，充分接近相变，最接近原点的H0(x)中的奇点也是H1(x)中的奇点。有了这

19、个结果，x*很容易计算。虽然我们通常不具有用于H1(x)的闭合表达式，但是很容易导出它的反函数。将w = H1(x)和x =代入式（26）并重新排列，我们发现感兴趣的奇异点对应于的导数为零的点w*，这是它的一个解那么x*（并且因此s*）由等式（42）给出。注意，不能保证等式（43）具有有限解，并且如果不是，则Ps通常不会遵循等式（40）的形式。当我们正好处于系统的相变时，我们有，因此方程（43）的解给出w* = x* = 1-我们使用上述结果-和s*。我们可以使用在转变时x* = 1的事实来计算指数的值如下。通过在等式（42）中放置w = 1 +来扩展H1(w)关于w*= 1，我们发现其中我们

20、在相变时使用，只要0，这通常不是，这意味着H1(x)以及H0(x)具有形式其中=1/2。该指数与指数如下相关。等式（40）意味着H0(x)可以写成形式其中C是常数，并且假定最后（误差）项远小于第二项。该表达式中的第一项是有限多项式，因此在有限平面上没有奇异点; 奇异性存在于第二项中。使用该方程，指数可以写为其中用积分来代替总和，因为变大，并且是不完全的函数。以指定的顺序取极限并重新排列，得到不考率度分布，除了在消失的特殊情况下见式(44)。结果= 3/2已知为普通泊松随机图1，但不是其他度分布。F 邻居数和平均路径长度。我们现在转向计算距离随机选择的顶点m个步长的邻居的数目。如第二章A所示，第

21、一和第二最近邻的概率分布由函数和。通过扩展，第m个邻居的分布由生成，其中函数的m-1次迭代作用于其自身。如果我们将定义为第m个邻居的这个生成函数，那么我们有然后，第m阶最近邻居的平均数是随着初始条件= z =，这就告诉我们从该结果，我们可以对图上两个随机选择的顶点之间的最短路径的典型长度进行估计。当到达该距离的顶点的邻居的总数等于图上的顶点的数目时，即，当使用公式（51），这给了我们在和的常见情况下，这减少到这个结果只是近似的，有两个原因。首先，用于推导它的条件仅是近似; 确切的答案取决于图的详细结构。第二，它假设所有顶点都可以从随机选择的起始顶点到达。一般来说，这不会是真的。对于没有巨分量的

22、图形，肯定不是真的，方程（54）是无意义的。但是，即使有一个巨分量，通常不是这种情况：它填充整个图。因此，通过将等式（54）中的N替换为NS，可以给出的更好近似，其中S是巨分量占据的图的分数，如在第二章D中。尽管存在这样的缺点，但是存在方程（54）的许多显着特征。（1） 其表明对于所有随机图的平均顶点 - 顶点距离，无论度分布如何，应当根据= A + BlnN对数地与大小N成比例，其中A和B是常数。这个结果当然是众所周知的许多特殊情况。（2） 其展示出作为全局属性的平均距离可以仅根据第一和第二最近邻的平均数的知识来计算，这是本地属性。因此，可以通过在诸如熟人网络之类的图形上的纯本地测量并且根据

23、它们来经验地测量这些数字，以确定顶点之间的预期平均距离。至少对于一些网络，这给出了令人惊讶的真实平均距离的良好估计37。（3） 其展示出仅第一和第二最近邻的平均数对于平均距离的计算是重要的，并且因此具有完全不同的顶点度分布但是具有相同的和的值的两个随机图将具有相同的平均距离。对于之前讨论的纯理论示例图的情况，我们不能对和进行经验测量，但是我们仍然可以使用公式(54)来计算。在普通(泊松)随机图的情况下，例如我们从等式(12)中发现= z，并且= ln N / ln z，这是这种类型的图的标准结果1。对于具有根据截断幂定律度分布的图，等式(17)和由等式(21)和(22)给出，并且平均顶点-顶点

24、距离在极限，这变成注意，对于任何3，该表达式不具有有限正实数值，指示必须为度分布指定有限截止以在这样的图上获得良好定义的平均顶点 - 顶点距离。G 仿真结果。作为对本节结果的检查，我们对具有各种顶点度分布的随机图进行了广泛的计算机模拟。这样的图形是相对直接生成的。首先，我们生成一组N个随机数ki以表示图中N个顶点的度数。这些可以被认为是从它们各自的顶点出现的边的“stubs”。然后我们随机选择这些存根的对，并将图上的边连接起来。很容易看出，这将生成具有给定的顶点度集合的所有图形，具有相等的概率。唯一小的陷阱是度数的和必须是偶数，因为添加到图中的每个边必须具有两端。这不难设计。如果集合ki使得和

25、为奇数，我们只需将其丢弃并生成一个新集合。实际上，如果适用可以使用变换方法来生成表示具有任何期望的概率分布的顶点度的整数，或者可以不使用舍弃或混合方法45。例如，可以使用如下的两步混合变换/舍弃方法来生成服从等式（17）的幂律加截止形式的度。首先，我们生成随机整数k 1的分布与成比例的，使用变换46其中r是均匀分布在0r 1范围内的随机实数。第二，我们用概率接受这个数字，其中“接受”是指如果数字不被接受，我们丢弃它并根据等式（57）产生另一个，重复该过程直到一个被接受。在图4中，我们显示了对于和的各种不同值，对于根据式（17）分布的顶点度的无向单分布图的模拟中的巨分量的大小的结果。在同一图上，

26、我们还显示了由方程（34）和（35）的数值解导出的相同量的期望值。如图所示，模拟和理论之间的一致性非常好。 （图4：具有根据等式（17）分布的顶点度的随机图中的巨分量 的大小作为针对指数的五个不同值的截止参数的函数。点 是来自N = 个顶点的图的数值模拟的结果，实线是无 限图的理论值，方程（34）和（35）。模拟结果上的误差条小 于数据点。） 3、有向图。我们现在转向具有任意度分布的有向图。有向图的示例是万维网，因为在web上的两个页面之间的每个超链接仅在一个方向上。网络具有遵循幂律的度分布，如第一章所述。有向图引入了一个微妙的，不存在于无向的，当我们应用我们的生成函数形式时变得重要。在有向图中，不可能谈论“分量” - 即一组连接的顶点 - 因为即使顶点A可以通过以下方式到达：来自顶点B的边（有向），这不一定意味着可以从顶点A到达顶点B.对于有向图，分量的想法有两种正确的概括：从给定顶点可达到的顶点集合，以及从其可以到达给定顶点。我们将这些分别称为“外分量”和“内分量”。一个内分量也可以被认为是那些可以通过向后边而不是向前边到达的顶点，从指定的顶点。可以通过允许向前和向后遍历边来研究有向图（例如参见文献26）。然而，在这种情况下，图有效地变成无向的，应该用第二章的形式来对待。考虑到这些想法，我们现在