Geometric Random Graphs vs Inhomogeneous Random Graphs

摘要

We consider random graphs on the set of vertices placed on the discrete d-dimensional torus. The edges between pairs of vertices are independent, and their probabilities depend on the distance between the vertices. Hence, the probabilities of connections are naturally scaled with the total number of vertices via distance. We propose a model with a universal form of scaling, which yields a natural classification of the models. In particular, it allows us to identify the class models which fit naturally the theory of inhomogeneous random graphs. These models exhibit phase transition in change of the size of the largest connected component strikingly similar to the one in the classical random graph model. However, despite such similarities with G(n,p) the geometric random graphs are proved here to exhibit also a new type of phase transitions when it concerns the local characteristics, such as the number of triangles or the clustering coefficient.