Connectivity and percolation properties of stochastic networks

Abstract

The present thesis is devoted to the investigation of connectivity and percolation properties of random geometric graphs, i.e., graphs that are embedded in some Euclidean space. Related structures such as hard-core packings of particles are also considered. First, in Chapter 3, the family of creek-crossing graphs is introduced. It is shown that creek-crossing graphs based on a homogeneous Poisson point process are almost surely connected. Chapter 4 discusses properties of Euclidean first-passage percolation on connected random geometric graphs. In particular, the asymptotic behavior of the length of shortest paths is analyzed. It is shown that under certain sufficient conditions, shortest-path lengths in a large class of stationary and isotropic random geometric graphs grow at most linearly in the Euclidean distance between the endpoints with high probability. Next, in Chapters 5 and 6, methods from percolation theory are used to analyze properties of two models for non-overlapping particles, namely stationary Apollonian packings and configurations obtained from collective-rearrangement algorithms, respectively. In fixed-access telecommunication networks, it is a common approach to use connected random geometric graphs to model the underlying road network. In Chapter 7, asymptotic distributions of important cost functionals such as typical shortest-path lengths and longest branch lengths are derived. Additionally, certain characteristics of the road network influence the risk level in third-party liability insurance, see Chapter 8. Finally, in Chapter 9, an application of connected random geometric graphs in computational materials science is presented, where the consistency of the Aggregate Monte Carlo velocity-estimator is proven.