Journal
ADVANCES IN APPLIED PROBABILITY
Volume 38, Issue 1, Pages 59-75Publisher
APPLIED PROBABILITY TRUST
DOI: 10.1239/aap/1143936140
Keywords
random graph; branching process; giant component; power law
Categories
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available