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

具有任意度分布的随机图及其应用M.E.J.Newman,S.H.Strogatz,andD.J.Watts,Phys.Rev.E64,026118（2001）.近来关于社交网络和互联网的结构的工作已经集中关注具有与在过去广泛研究的泊松度分布显着不同的顶点度的分布的图。在本文中，我们详细地开发具有任意度分布的随机图的理论。除了简单的无向，单向图，我们考查定向和二分图的属性。在其他结果中，我们得到精确表达式，其中巨分量首先形成的相变的位置，平均分量大小，巨分量的大小（如果有的话），距离随机选择的顶点一定距离的顶点的平均数量，以及图中顶点-顶点距离的平均。我们将我们的理论应用于一些真实世界的图形，包括科学家和财富1000强公司董事的全球网络和协作图。我们证明，在某些情况下随机图与适当的顶点度分布预测是令人惊讶的准确性的现实世界的行为，而在其他人有一个可衡量的理论与现实之间的差异，可能表明网络中的额外的社会结构的存在不被随机图捕获。1、介绍。随机图[1]是点或顶点的集合，具有线或边，其随机连接它们的对[图1(a)]。随机图的研究有悠久的历史。从二十世纪五十年代和二十世纪六十年代Erdo和Re'nyi的有影响力的工作开始，随机图论已经发展成为现代离散数学的支柱之一，并产生了大量的结果，它们许多非常巧妙，描述了图形的统计特性，例如组件尺寸的分布，巨分量（giantcomponent）的存在和大小以及典型的顶点-顶点距离。在几乎所有这些研究中，已经假设两个顶点之间的边的存在或不存在与任何其它边的存在或不存在无关，使得每个边可以被认为以独立的概率p存在。如果在图中存在N个顶点，且每个顶点平均连接z条边，则显然p=z/（N-1）是很平常的，其对于大的N通常由z/N近似。连接到任何特定顶点的边的数量被称为该顶点的度k，并且具有由下式给出的概率分布pk其中第二等式在大N的极限中变得精确。这种分布我们认为是泊松分布：普通随机图顶点度具有泊松分布，这是一个关键点，正如我们现在解释的。随机图形不仅仅是一个数学玩具;它们已广泛用作各种类型的现实世界网络的模型，特别是在流行病学中。疾病通过社区的传播强烈依赖于感染该疾病的人和对其感染的人之间的接触模式。该模式可以描述为网络，其中个体由能够通过边传播疾病的顶点和接触表示。被称为易感/感染/恢复模型的大类流行病学模型[5-7]经常使用所谓的完全混合近似，这是假设接触是随机和不相关的，即它们形成随机图。然而，随机图表证明具有作为这种现实世界现象的模型的严重缺点。虽然很难通过实验确定疾病传播的联系网络的结构[8]，已经对其他社会网络进行了研究，例如各种社区内的友谊网络[9-11]，网络电话呼叫[12,13]，航空公司时间表[14]和电网[15]，以及物理或生物系统网络，包括神经网络[15]，聚合物的结构和构象空间[16,17]，代谢途径[18,19]和食物网[20,21]。发现[13,14]在许多这些网络中的顶点度的分布与泊松分布-通常是巨大的不同-可测量不同-这强烈暗示，如其他地方[22]所强调的，这样的网络，我们会错过，如果我们用普通（泊松）随机图来近似它们。（图1:（a）随机图的示意图，圆表示顶点，线表示边。（b）有向随机图，即其中每个边仅在一个方向上延伸的随机图。）另一个广泛研究的网络是互联网，其结构已经吸引了非常大量的细查，学术和其他方面，从1993年开始疾速上升到公众可见度。世界各地的网页可以被认为是一个图形和它们之间的超链接作为边。经验研究[23-26]已经表明，该图具有顶点度的分布，其是严重偏斜的并且具有指数在-2和-3之间的脂肪（幂律）尾。（互联网的基础物理结构也具有这种类型的度分布）这种分布不同于泊松，因此我们预期简单的随机图给出网络的结构性质的非常差的近似。然而，网络在另一方面与随机图不同：它是定向的。网络上的链接从一个页面到另一个页面只在一个方向上引导[参见图1(b)]。如Broder等人[26]，这对一个页面从另一个页面的典型可访问性有重大的实际影响，这种效果也不会被简单的（无向）随机图模型捕获。已经吸引细查的另一类网络是协作网络类。这种网络的例子包括公司董事会[28-31]，公司共同所有权网络[32]，科学家[33-37]和电影演员[15]的合作。除了具有强非泊松度分布[14,36]，这些网络具有二分体结构;在图上存在两种不同类型的顶点，其中链接仅在不同种类的顶点之间运行[38]，参见图2。例如，在电影演员的情况下，两种类型的顶点是电影和演员，并且网络可以表示为具有在每个电影和出现在其中的演员之间运行的边的图形。研究人员还考虑了这个图的投影到仅仅演员的单一空间，也称为单模网络[38]。在这样的投影中，两个演员被认为是连接的，如果他们一起出现在电影中。然而，单模式网络的构造涉及丢弃包含在原始二分网络中的一些信息，并且出于这个原因，更期望使用完全二分体结构来模型化协作网络。考虑到目前在这里描述的许多图的结构的高度关注[39]，并且给定它们与在过去研究的普通随机图的实质性差异，如果我们可以推广数学的随机图到非泊松度分布，以及定向和二分图。在本文中，我们只是这样做，详细说明了每个这些图类型的统计属性如何可以精确计算在大图规模的限制下。我们还举例说明了我们的理论应用于一些真实世界网络的建模，包括和协作图。（图2：二分图的示意图（左），例如电影和出现在其中的演员的图。在这个小图中，我们有四个电影，标记为1到4，和11个演员，标记为A到K，边将每个电影连接到演员的演员。在图片的右半部分，我们显示了11个演员的图形的单模式投影。）2、具有任意度分布的随机图。在本节中，我们开发了一种公式，用于计算各种数量，包括局部和全局的大型单向无向图，其顶点的度具有任意概率分布。在所有方面，除了它们的度分布之外，这些图被假定为完全随机的。这意味着所有顶点的度是从指定分布绘制的独立的相同分布的随机整数。对于这些度的给定选择，也称为“度序列”，从具有该度序列的所有图的集合中随机均匀地选择图。在本文中计算的所有属性在以这种方式生成的图的集合上被平均。在大图规模的限制中，等价过程是仅研究一个特定度序列，在具有该序列的所有图上均匀地平均，其中选择该序列以尽可能接近期望的概率分布。后一个过程可以被认为是随机图的“微规则集合”，其中前者是一个“规范集合”。对任意度分布的随机图一些结果是已知的：在两个美丽的最近的论文[40,41]，Molloy和Reed已经得出了巨分量首次出现的相变位置的公式，以及巨分量的大小。（这些结果是在微规模集合内计算的，但同样适用于大系统大小限制中的规范）。本文中提出的公式给出了这些结果的另一种推导，也提供了一个获得其他感兴趣的量的框架，其中一些我们计算。在第三和第四章中，我们将公式扩展到有向图（例如万维网）和二分图（例如协作图）的情况。A生成函数。我们的方法基于生成函数[42]，对于我们的目的其中最根本的，是生成函数)(0xG的顶点度k的概率分布。假设我们有一个不可分无向图-一个熟人网络，例如大的N，N个顶点。我们定义其中pk是图上随机选择的顶点具有度k的概率。假设分布pk正确地归一化，因此对于这里考虑的所有生成函数也是如此，只有一些重要的例外，我们将在适当的点注释。因为概率分布是归一化的和正定的，)(0xG对于所有|x|1也是绝对收敛的，因此在该区域中没有奇点。本文的所有计算将局限于|x|1的区域。函数)(0xG以及实际上任何概率生成函数具有许多属性将证明在后续开发中有用的。导数。概率pk由G0的第k阶导数给出因此一个函数)(0xG概括包含离散概率分布kp的所有信息，我们说函数)(0xG“生成”概率分布kp。矩。由生成函数生成的概率分布的平均值-例如，在)(0xG的情况下的顶点的平均度z由下式给出：因此，如果我们可以计算生成函数，我们也可以计算它生成的概率分布的平均值。也可以从更高的导数计算更高的分布矩。一般来说，我们有幂。如果通过给定生成函数生成对象的属性k的分布，则通过该生成函数的m次幂生成对对象的m次独立实现之间总和为k的分布。例如，如果我们从大图中随机选择m个顶点，则这些顶点的度的和的分布由mxG)(0生成。为了看到为什么会这样，考虑只有两个顶点的简单情况。单个顶点的生成函数的平方20)(xG可以扩展为很清楚，该表达式中nx的幂的系数正好是所有乘积kjpp的和，使得j+k=n，因此正确地给出两个顶点的度的和为n的概率。简单地说服自己，这个属性也扩展到生成函数的所有更高的幂。所有这些属性将用于本文中给出的推导。对我们来说另一个重要的量是通过随机选择的边到达的顶点的度分布。这样的边以与该顶点的度成比例的概率到达顶点，因此顶点具有与kpk成比例的度的概率分布。正确归一化的分布由生成。如果我们从随机选择的顶点开始并沿着该顶点的每个边到达k个最近邻居，则到达的每个顶点具有由该函数剩余输出边生成的分布，除以x的一次幂，以允许对于我们到达的边。因此，输出边的分布由函数生成其中z是平均顶点度，如前所述。这些输出边中的任何一个连接到我们开始的原始顶点或者其任何其他直接邻居的概率为1N，因此可以在大N的极限中被忽略。因此，利用上述生成函数的“幂”属性，用于原始顶点的第二邻居的数目的概率分布的生成函数可以被写为类似地，第三最近邻的分布由)))(((110xGGG生成，等等。第二邻居的平均数2z是其中我们已经利用了事实：.1)1(1G（可能有人试图推测，由于第一相邻的平均数是)1(0G，等式（5），以及第二相邻的平均数是)1(0G，方程（11），那么第m个邻居的平均数应该由在x=1时评估的0G的第m个导数给出，然而，如第二章F所示，这个猜想是错误的。）B例子。为了使事情更具体，我们立即介绍一些具体图表的例子来说明如何进行这些计算。(a)Poisson分布图。这种类型的图形的最简单的例子是其中度分布是二项式的，或者是在大N极限中的泊松。这种分布产生了许多数学家研究的标准随机图，并在第一章中讨论。在该图中任何两个顶点之间的边的存在的概率p=z/N对于所有顶点是相同的，并且)(0xG由其中最后的等式适用于极限N→。然后平凡的表明顶点的平均度确实是.)1(0zG，度的概率分布由!kezpzkk给出，这是普通泊松分布。还要注意对于这种特殊情况，我们有)()(01xGxG，使得在一个顶点的输出边的分布是相同的，不管我们是通过随机选择一个顶点到达那里，或者随机选择边。这个属性是泊松分布随机图所特有的，这就是为什么这种随机图的理论特别简单的原因。(b)指数分布图。也许下一个最简单的类型图是顶点度具有指数分布的图其中是常数。此分布的生成函数是具有指数度分布的图的示例在第五章A中给出。(c)幂律分布图。最近对网络和社会网络的属性的兴趣导致我们调查顶点度具有幂律分布的图的属性。这样的图形已经讨论由Baraba's与同事[22,23]和Aiello等人[13]。在本文中，我们将看到度分布由下式给出的图其中C，和是常数。包含指数截止的原因有两个：首先许多真实世界的图似乎显示出这个截止[14,36];第二，对所有它使得分布可归一化，而不只是2。常数C通过归一化的要求而固定，得到，于是其中)(xLin是x的第n个多重对数函数。[对于那些不熟悉这个函数的人来说，它对于我们的目的的突出特征在于，对于所有n，在x=0处是零并且在0x1的范围内是实数，有限和单调递增。它也随着n的增加而减小，并且对于n1仅在x=1处具有极点，尽管其在n=1下具有有效的分析延续，其在x=1处取值)(n。]将式（17）代入式（2），我们发现具有这种度分布的图的生成函数是在极限→中，参考文献[13]和[23]中考虑的情况-简化为其中)(是黎曼函数。函数)(1xG由下式给出因此，例如，随机选择的顶点的邻居的平均数量是第二邻居的平均数为(d)具有任意指定度分布的图。在某些情况下，我们希望模拟具有已知度分布的特定现实世界图-因为我们可以直接测量它们。引言中描述的许多图属于此类别。对于这些图，我们知道具有度