On Statistical Properties of a New Family of Geometric Random Graphs

We define a new family of random geometric graphs which we call random covering graphs and study its statistical properties. To the best of our knowledge, this family of graphs has not been explored in the past. Our experimental results suggest that there are striking deviations in the expected number of edges, degree distribution, spectrum of adjacency/normalized Laplacian matrix associated with the new family of graphs as compared to both the well-known Erdos–Renyi random graphs and the general random geometric graphs as originally defined by Gilbert. Particularly, degree distribution of the graphs shows some interesting features in low dimensions. To the more applied end, we believe that our random graph family might be effective in modelling some practically useful networks (world wide web, social networks, railway or road networks, etc.). It is observed that the degree distribution of some complex networks arising in practice follow power law distribution or log power distribution; they tend to be right skewed, having a heavy tail unlike the degree distribution of Erdos–Renyi graphs or general geometric random graphs (which follow exponential distribution with a sharp tail). The degree distribution of our random graph family significantly deviates from that of Erdos–Renyi graphs or general geometric random graphs and is closer to a right-skewed power law distribution with a heavy tail. Thus, we believe that this new family of graphs might be more effective in modelling the typical real-world networks mentioned above. The key contribution of the paper is introducing this new random graph family and studying some of its properties experimentally, further investigation into which would be interesting from a purely mathematical perspective. Also, it might be of practical interest in terms of modelling real-world networks.