Connectivity of inhomogeneous random graphs1. Issue 3 (26th February 2013) - Devroye, Luc
Abstract We find conditions for the connectivity of inhomogeneous random graphs with intermediate density. Our results generalize the classical result for G(n, p), when p=clogn/n. We draw n independent points Xi from a general distribution on a separable metric space, and let their indices form the vertex set of a graph. An edge (i, j) is added with probability min(1, κ(Xi, Xj)logn/n), where κ≥0 is a fixed kernel. We show that, under reasonably weak assumptions, the connectivity threshold of the model can be determined. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 408‐420, 2014