Connectivity of inhomogeneous random graphs1. Issue 3 (26th February 2013) - Devroye, Luc; Fraiman, Nicolas
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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh12v95q8g" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p=clogn/n</alternatives>. 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh12v95qbk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />min(1, κ(Xi, Xj)logn/n)</alternatives>, where <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh12v95qwd" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />κ≥0</alternatives> 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