Geometric Random Graphs vs Inhomogeneous Random Graphs

G.M. Napolitano, T.S. Turova

2019, v.25, Issue 4, 615-638

ABSTRACT

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.

Keywords: inhomogeneous random graphs, distance random graphs, phase transitions in random graphs

COMMENTS

Please log in or register to leave a comment