Sparse Random Graphs with Clustering
Sparse Random Graphs with Clustering
复制标题
DOI：
10.1002/rsa.20322
复制
发表时间：
2011-05-01
影响因子：
1
通讯作者：
Riordan, Oliver
中科院分区：
文献类型：
--
作者：
Bollobas, Bela;Janson, Svante;Riordan, Oliver
在2007年，我们引入了一个稀疏随机图的一般模型，边之间具有（条件）独立性。本文的目的是提出一个扩展的边缘是远离独立的这个模型，并证明了几个结果，这种扩展。其基本思想是通过添加边和其他小图来构造随机图。换句话说，我们首先构造一个具有（条件）独立超边的非齐次随机超图，然后用一个（可能是完全的）图替换每个超边。虽然足够灵活，可以生成边之间具有显著相关性的图，但该模型在数学上仍然是易于处理的。事实上，我们找到了一个巨大的组件出现在充分的一般性的临界点，在一定的积分算子的规范，并涉及的巨大的组件的生存概率的某个（非泊松）多类型的分支过程的大小。虽然我们的主要重点是相变，我们也研究了度分布和小的子图的数量。我们用一个简单的特例来说明这个模型，这个特例产生了幂律度序列的图，它具有广泛的度指数和聚类系数。(c)2010 Wiley Periodicals，Inc.随机结构算法，38，269-323，2011
In 2007, we introduced a general model of sparse random graphs with (conditional) independence between the edges. The aim of this article is to present an extension of this model in which the edges are far from independent, and to prove several results about this extension. The basic idea is to construct the random graph by adding not only edges but also other small graphs. In other words, we first construct an inhomogeneous random hypergraph with (conditionally) independent hyperedges, and then replace each hyperedge by a (perhaps complete) graph. Although flexible enough to produce graphs with significant dependence between edges, this model is nonetheless mathematically tractable. Indeed, we find the critical point where a giant component emerges in full generality, in terms of the norm of a certain integral operator, and relate the size of the giant component to the survival probability of a certain (non-Poisson) multi-type branching process. While our main focus is the phase transition, we also study the degree distribution and the numbers of small subgraphs. We illustrate the model with a simple special case that produces graphs with power-law degree sequences with a wide range of degree exponents and clustering coefficients. (c) 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 269-323, 2011