The size of the giant component of a random graph with a given degree sequence
The size of the giant component of a random graph with a given degree sequence
复制标题
DOI：
10.1017/s0963548398003526
复制
发表时间：
1998-09-01
影响因子：
0.9
通讯作者：
Reed, B
中科院分区：
文献类型：
--
作者：
Molloy, M;Reed, B
给定一个非负实数序列lambda(0)，lambda(1)，.在[12]中，作者本质上证明了如果Sigma i(i-2)lambda(I)>；0，则图A.S.有一个巨大的分量，而如果Sigma I(i-2)lambda(I)<；0，则A.S.图表中的所有组件都很小。本文分析了前一种情况下的巨分量的大小，以及删除该分量所形成的图的结构。我们测定了epsilon，lambda(0)‘，lambda(1)’.以使A.S.图的巨大分支C有epsilon n+o(N)个顶点，删除C后剩下的图的结构基本上是具有n‘=n-\C个顶点的随机图的结构，其中lambda(I)’n‘为i度.
Given a sequence of nonnegative real numbers lambda(0),lambda(1),.. that sum to 1, we consider a random graph having approximately lambda(i)n vertices of degree i. In [12] the authors essentially show that if Sigma i(i - 2)lambda(i) > 0 then the graph a.s. has a giant component, while if Sigma i(i - 2)lambda(i) < 0 then a.s. all components in the graph are small. In this paper we analyse the size of the giant component in the former case, and the structure of the graph formed by deleting that component. We determine epsilon,lambda(0)',lambda(1)'... such that a.s. the giant component, C, has epsilon n + o(n) vertices, and the structure of the graph remaining after deleting C is basically that of a random graph with n' = n - \C\ vertices, and with lambda(i)'n' of them of degree i.