The Cut Metric, Random Graphs, and Branching Processes
The Cut Metric, Random Graphs, and Branching Processes
复制标题
剪切度量、随机图和分支过程
DOI：
10.1007/s10955-010-9982-z
复制
发表时间：
2009
影响因子：
1.6
通讯作者：
O. Riordan
中科院分区：
文献类型：
--
作者：
B. Bollobás;S. Janson;O. Riordan
在本文中，我们研究边相互独立的随机图的组件结构。在温和的假设下，我们确定是否存在一个巨型组件，并在其存在时找到它的渐近大小。我们假设边概率矩阵序列收敛到一个合适的极限对象（一个核），但只是在一种非常弱的意义下，即割度量意义下。因此，我们的结果推广了作者在《随机结构与算法》31:3 - 122 (2007)中引入的已经非常一般的非齐次随机图模型中关于相变的先前结果，以及博洛巴斯、博格斯、蔡斯和赖尔登（《概率论年刊》38:150 - 183, 2010）的相关结果，所有这些都涉及相当强的假设。我们还证明了随机超图的相应结果；这些结果推广了我们关于具有聚类的非齐次随机图中相变的结果（《随机结构与算法》，2010，即将发表）。
In this paper we study the component structure of random graphs with independence between the edges. Under mild assumptions, we determine whether there is a giant component, and find its asymptotic size when it exists. We assume that the sequence of matrices of edge probabilities converges to an appropriate limit object (a kernel), but only in a very weak sense, namely in the cut metric. Our results thus generalize previous results on the phase transition in the already very general inhomogeneous random graph model introduced by the present authors in Random Struct. Algorithms 31:3–122 (2007), as well as related results of Bollobás, Borgs, Chayes and Riordan (Ann. Probab. 38:150–183, 2010), all of which involve considerably stronger assumptions. We also prove corresponding results for random hypergraphs; these generalize our results on the phase transition in inhomogeneous random graphs with clustering (Random Struct. Algorithms, 2010, to appear).