Small-world and ultrasmall-world phenomena in kernel-based spatial random graphs

Abstract

In this thesis, we examine the kernel-based spatial random graph (KSRG) model, which is a generalisation of many known models such as long-range percolation, scale-free percolation, the Poisson Boolean model and age-based spatial preferential attachment. We construct a KSRG from a vertex set V = Z^d, assigning each vertex v ∈ V a weight Wv according to a power-law with parameter τ − 1 and connecting each pair of vertices conditionally independently according to
P(u ↔ v|Wu,Wv) = Θ(1 ∧(max {Wu,Wv}^(σ1) min {Wu,Wv}^(σ2)/|u − v|^d))^α.
Our first contribution is to show that, under certain choices of the parameters σ1, σ2, τ and α, the graph distance is at most poly-logarithmic or at most doubly logarithmic when compared to the spatial distance. Furthermore, the parameters σ1 and σ2 allow for extra degrees of freedom when compared to the models mentioned earlier, which yields a new exponent for poly-logarithmic distances and a generalised constant for doubly logarithmic distances. Our second contribution lies in the techniques used to prove these results. In particular, we show that with probability tending to 1 there is a subset of vertices that behaves pseudo-randomly with regards to the expected amount of vertices with a given weight in any radius. The presence of this subset, which we call a net, allows for the avoidance of the use of FKG-like inequalities in proofs. Primarily, it allows us to reveal all relevant weights in advance, which allows us to disregard many correlations that we would otherwise need to take into account during construction of paths.