On a conditionally Poissonian graph process 论文

摘要

Random (pseudo)graphs G N with the following structure are studied: first, independent and identically distributed capacities Λ 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(Λ i Λ j / ∑ k =1 N Λ k ). The main result of the paper is that when P(Λ 1 > x) ≥ x −τ+1 , where τ ∈ (2, 3), then, asymptotically almost surely, G N 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 (τ − 2)). It is also shown that the cases τ > 3, τ ∈ (2, 3), and τ ∈ (1, 2) present three qualitatively different connectivity architectures.