Connectivity of Inhomogeneous Random K-Out Graphs

Abstract: We propose inhomogeneous random K-out graphs

m a t h b b H (n; p m b m u, p m b K_{n})

, where each of the

n

nodes is assigned to one of

r

classes independently with a probability distribution

p m b m u = m u_{1}, l d o t s, m u_{r}

. In particular, each node is classified as class-

i

with probability

m u_{i} > 0

, independently. Each class-

i

node selects

K_{i, n}

distinct nodes uniformly at random from among all other nodes. A pair of nodes are adjacent in

m a t h b b H (n; p m b m u, p m b K_{n})

if at least one selects the other. Without loss of generality, we assume that

K_{1, n} l e q K_{2, n} l e q l d o t s l e q K_{r, n}

. Earlier results on homogeneous random K-out graphs

m a t h b b H (n; K_{n})

, where all nodes select the same number

K

of other nodes, reveal that

m a t h b b H (n; K_{n})

is connected with high probability (whp) if

K_{n} g e q 2

which implies that

m a t h b b H (n; p m b m u, p m b K_{n})

is connected whp if

K_{1, n} g e q 2

. In this paper, we investigate the connectivity of inhomogeneous random K-out graphs

m a t h b b H (n; p m b m u, p m b K_{n})

for the special case when

K_{1, n} = 1

, i.e., when each class-

1

node selects only one other node. We show that

m a t h b b H l e f t (n; p m b m u, p m b K_{n} i g h t)

is connected whp if

K_{r, n}

is chosen such that

l i m_{n o i n f t y} K_{r, n} = i n f t y

. However, any bounded choice of the sequence

K_{r, n}

gives a positive probability of

m a t h b b H l e f t (n; p m b m u, p m b K_{n} i g h t)

being not connected. Simulation results are provided to validate our results in the finite node regime.

Cited in

(2)

This page was built for publication: Connectivity of Inhomogeneous Random K-Out Graphs