Connectivity and giant component in random distance graphs
Various different random graph models have been proposed in which the vertices of the graph are seen as members of a metric space, and edges between vertices are determined as a function of the distance between the corresponding metric space elements. We here propose a model G=G(X,f), in which (X,d) is a metric space, V(G)=X, and P(u∼v)=f(d(u,v)), where f is a decreasing function on the set of possible distances in X. We consider the case that X is the n×n×⋯×n integer lattice in dimension r, with d the ℓ1 metric, and f(d)=nβd1, and determine a threshold for the emergence of the giant component and connectivity in this model. We compare this model with a traditional Waxman graph. Further, we discuss expected degrees of nodes in detail for dimension 2.