Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs

Abstract

A recent trend in the context of graph theory is to bring theoretical analyses closer to empirical observations, by focusing the studies on random graph models that are used to represent practical instances. There, it was observed that geometric inhomogeneous random graphs (GIRGs) yield good representations of complex real-world networks, by expressing edge probabilities as a function that depends on (heterogeneous) vertex weights and distances in some underlying geometric space that the vertices are distributed in. While most of the parameters of the model are understood well, it was unclear how the dimensionality of the ground space affects the structure of the graphs. In this paper, we complement existing research into the dimension of geometric random graph models and the ongoing study of determining the dimensionality of real-world networks, by studying how the structure of GIRGs changes as the number of dimensions increases. We prove that, in the limit, GIRGs approach non-geometric inhomogeneous random graphs and present insights on how quickly the decay of the geometry impacts important graph structures. In particular, we study the expected number of cliques of a given size as well as the clique number and characterize phase transitions at which their behavior changes fundamentally. Finally, our insights help in better understanding previous results about the impact of the dimensionality on geometric random graphs.

References in corpus (11)

• Clustering and preferential attachment in growing networks
• Hyperbolic Geometry of Complex Networks
• Random Geometric Graphs
• Scale-free Networks Well Done
• True scale-free networks hidden by finite size effects
• Principled approach to the selection of the embedding dimension of networks
• A multivariate Berry--Esseen theorem with explicit constants
• Detecting the ultra low dimensionality of real networks
• Dimensionality of social networks using motifs and eigenvalues
• Random geometric graphs in high dimension
• Cliques in geometric inhomogeneous random graph

Cited by in corpus (1)

• Entropy of Random Geometric Graphs in High and Low Dimensions