Connectivity of Inhomogeneous Random K-Out Graphs
Rashad Eletreby, Osman Yağan · IEEE Transactions on Information Theory · 2019
We investigate the connectivity of inhomogeneous random K-out graphs, denoted H(n;μ,Kn), where each of the n nodes is assigned to a class i = 1, ..., r independently according to a probability distribution μ = {μ1, ..., μr}. Each class-i node chooses Ki,ndistinct nodes uniformly at random from among all other nodes. A pair of nodes are adjacent in H(n;μ,Kn) if at least one selects the other. Without loss of generality, we assume that K1,n≤ K2,n≤ ... ≤ Kr,n. From earlier results on homogeneous random K-out graphs (where all nodes choose the same number K of nodes), it is known that H(n;μ,Kn) is connected with high probability (whp) if Kn≥ 2. In this paper, we study the case where K1,n= 1 and seek conditions on K2,n, ..., Kr,n, and μ such that the resulting graph is connected. We show that H(n;μ,Kn) is connected whp if Kr,nis chosen such that limn→∞Kr,n= ∞. However, any bounded choice of the sequence Kr,ngives a positive probability of H(n;μ,Kn) being not connected. A numerical study is provided to validate our results in the finite node regime.