Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1.

Abstract: Consider the random graph on

n

vertices

1, ..., n

. Each vertex

i

is assigned a type

X_{i}

with

X_{1}, ..., X_{n}

being independent identically distributed as a nonnegative discrete random variable

X

. We assume that

. Given types of all vertices, an edge exists between vertices

i

and

j

independent of anything else and with probability

m i n 1, f r a c X_{i} X_{j} n (1 + f r a c a n^{1 / 3})

. We study the critical phase, which is known to take place when

. We prove that normalized by

n^{- 2 / 3}

the asymptotic joint distributions of component sizes of the graph equals the joint distribution of the excursions of a reflecting Brownian motion

B^{a} (s)

with diffusion coefficient

and drift

. This shows that finiteness of

is the necessary condition for the diffusion limit. In particular, we conclude that the size of the largest connected component is of order

n^{2 / 3}

.

Cites Work

Cited In (14)

This page was built for publication: Diffusion approximation for the components in critical inhomogeneous random graphs of rank 1.