Connectivity and giant component in random distance graphs

Abstract

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 $\mathbb{P}(u\sim 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\times n\times \cdots \times n$ integer lattice in dimension $r$, with $d$ the ${\ell }_1$ metric, and $f(d)=\frac{1}{n^{\beta }d}$, 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.

References in corpus (5)

• Kronecker Graphs: An Approach to Modeling Networks
• Multiplicative Attribute Graph Model of Real-World Networks
• Geographical threshold graphs with small-world and scale-free properties
• Modeling Social Networks with Node Attributes using the Multiplicative Attribute Graph Model
• A simple branching process approach to the phase transition in $G_{n,p}$