On a conditionally Poissonian graph process

• DOI: 10.1239/aap/1143936140
• Publication Date: 2006-04-04T03:43:57Z
• Authors: Ilkka Norros; Hannu Reittu
• Keywords: Giant component; Connected component; Component (thermodynamics)

Random (pseudo)graphs G N with the following structure are studied: first, independent and identically distributed capacities Λ i drawn for vertices = 1, …, ; then, each pair of ( , j ) is connected, independently other pairs, E edges, where has distribution Poisson(Λ / ∑ k =1 ). The main result paper that when P(Λ 1 > x) ≥ x −τ+1 τ ∈ (2, 3), asymptotically almost surely, a giant component, distance between two randomly selected component less than (2 + o ))(log log )/(-log (τ − 2)). It also shown cases 3, (1, 2) present three qualitatively different connectivity architectures.