Random Geometric Graphs

University Of Memphis, Memphis TN

Investigators

Abstract

The aim of this project is to further the study of random geometric graphs. This subject has grown out of applied problems, with the first questions about the way fluids seep through porous media. More recently, many questions about random geometric graphs have been prompted by the study of large scale electronic and communication networks. The basic model of random geometric graphs was proposed by Gilbert over fifty years ago: take points randomly in the plane according to a Poisson point process of intensity 1, and join two whenever they are within a distance r of each other. The main question Gilbert asked is the following: for what values of r do we obtain an infinite connected component? Surprisingly, even after fifty years, only rather poor upper and lower bounds are known for the critical value of r. Some properties of this Gilbert model are known, but many other questions still remain unanswered. The proposed project considers some of these questions, and many other questions about related models of random graph inspired by both percolation theory and large scale communication networks. Random geometric graphs can be used to model many large scale networks that exist in real life, such as the internet, social networks, and are particularly suited to the modeling of large scale sensor and transceiver networks. As electronic devices become smaller and cheaper, it is now not uncommon to have very large networks of interconnected devices. Modeling the behavior of these networks is becoming more and more important, and the analysis of the behavior of these networks when they become extremely large is becoming increasingly relevant in real world applications. The research proposed will aid the understanding of the properties of these large scale networks.