On a conditionally poissonian graph process
On a conditionally poissonian graph process
复制标题
DOI：
10.1239/aap/1143936140
复制
发表时间：
2006-03-01
影响因子：
1.2
通讯作者：
Reittu, H
中科院分区：
文献类型：
--
作者：
Norros, I;Reittu, H
研究了具有以下结构的随机（伪）图G(N)：首先，对顶点i = 1，…绘制独立且分布相同的容量Lambda(i)N;然后,每一对顶点(i, j)连接,独立于其他双E (i, j)边缘,E (i, j)泊松分布(λ(i)λ(j) /σ(N)λk (k = 1)。论文的主要结果是,当P(λ(1)> x) > = x(τ)+ 1),τ是一种元素的(2、3),然后,渐近几乎肯定,GN有一个巨大的组件,和两个随机选择的顶点之间的距离的组件小于(2 + o (N))(日志o (log N)) /(日志(τ- 2))。还表明，在tau > 3、tau是（2,3）的元素和tau是（1,2）的元素的情况下，呈现出三种性质不同的连接架构。
Random (pseudo)graphs G(N) with the following structure are studied: first, independent and identically distributed capacities Lambda(i) are drawn for vertices i = 1,..., N; then, each pair of vertices (i, j) is connected, independently of the other pairs, with E(i, j) edges, where E(i, j) has distribution Poisson(Lambda(i)Lambda(j)/Sigma(N)(k=1) Lambda k. The main result of the paper is that when P(Lambda(1) > x) >= x(-tau+1), where tau is an element of (2, 3), then, asymptotically almost surely, GN has a giant component, and the distance between two randomly selected vertices of the giant component is less than (2 + o(N))(log log N)/(-log (tau - 2)). It is also shown that the cases tau > 3, tau is an element of (2, 3), and tau is an element of (1, 2) present three qualitatively different connectivity architectures.