非齐次随机图中的相变

摘要 “经典”随机图模型，尤其是 G ( n , p )，在某种意义上是“齐次的”，即（例如）度数往往集中在一个典型值附近。现实世界中出现的许多图并不具备这一性质，例如具有幂律度分布。因此，近年来人们对定义和研究“非齐次”随机图模型产生了浓厚的兴趣。在这些新模型中，研究最广泛的性质之一是它们的“稳健性”，或者等价地，随着边密度参数变化时的“相变”。对于 G ( n , p )（p = c / n），c = 1 处的相变在过去的40多年中一直是随机图研究的核心课题。许多新的非齐次模型相当复杂；尽管存在例外，但在大多数情况下，诸如精确确定相变的临界点等精确问题，只有在边之间存在独立性时才是可解决的。幸运的是，一些已研究的模型已经具备这一性质，而其他模型可以通过具有独立性的模型进行逼近。在此，我们引入了一种非常通用的非齐次随机图模型，其边之间具有（条件）独立性，并进行了尺度缩放，使得边的数量与顶点数量呈线性关系。这种缩放对应于用于研究相变的 G ( n , p ) 的 p = c / n 缩放；此外，它似乎也是许多大型现实世界图的一个性质。我们的模型将许多先前研究的模型作为特例包含在内。我们表明，在一个非常弱的假设下（即边的期望数量是“符合预期的”），该模型的许多性质都可以被确定，特别是相变的临界点以及相变之上巨分支的大小。我们通过将我们的随机图与更容易分析的分支过程联系起来实现了这一点。我们还考虑了该模型的其他性质，例如证明当存在巨分支时，它是“稳定的”：对于一个典型的随机图，无论我们如何添加或删除 o ( n ) 条边，巨分支的大小变化都不会超过 o ( n )。© 2007 Wiley Periodicals, Inc. Random Struct. Alg., 31, 3–122, 2007