Statistical mechanics of random geometric graphs: Geometry-induced first order phase transition

Abstract

Random geometric graphs (RGG) can be formalized as hidden-variables models where the hidden variables are the coordinates of the nodes. Here we develop a general approach to extract the typical configurations of a generic hidden-variables model and apply the resulting equations to RGG. For any RGG, defined through a rigid or a soft geometric rule, the method reduces to a non trivial satisfaction problem: Given $N$ nodes, a domain $\mathcal{D}$, and a desired average connectivity $⟨k⟩$, find - if any - the distribution of nodes having support in $\mathcal{D}$ and average connectivity $⟨k⟩$. We find out that, in the thermodynamic limit, nodes are either uniformly distributed or highly condensed in a small region, the two regimes being separated by a first order phase transition characterized by a $O(N)$ jump of $⟨k⟩$. Other intermediate values of $⟨k⟩$ correspond to very rare graph realizations. The phase transition is observed as a function of a parameter $a\in [0,1]$ that tunes the underlying geometry. In particular, $a=1$ indicates a rigid geometry where only close nodes are connected, while $a=0$ indicates a rigid anti-geometry where only distant nodes are connected. Consistently, when $a=1/2$ there is no geometry and no phase transition. After discussing the numerical analysis, we provide a combinatorial argument to fully explain the mechanism inducing this phase transition and recognize it as an easy-hard-easy transition. Our result shows that, in general, ad hoc optimized networks can hardly be designed, unless to rely to specific heterogeneous constructions, not necessarily scale free.

arXiv comment14 pages, 5 figures

References in corpus (17)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Critical phenomena in complex networks
• Hyperbolic Geometry of Complex Networks
• The statistical mechanics of networks
• Random Geometric Graphs
• Class of correlated random networks with hidden variables
• The entropy of randomized network ensembles
• Statistical-mechanical approach to subgraph centrality in complex networks
• Solution of the 2-star model of a network
• All scale-free networks are sparse
• Emergence of large cliques in random scale-free network
• Deciphering the global organization of clustering in real complex networks
• Analytic solution of a static scale-free network model
• Entropy distribution and condensation in random networks with a given degree distribution
• Fluctuations analysis in complex networks modeled by hidden variable models. Necessity of a large cut-off in hidden-variable models
• Fluctuations of motifs and non self-averaging in complex networks. A self- vs non-self-averaging phase transition scenario

Cited by in corpus (5)

• The shape of shortest paths in random spatial networks
• Random geometric graphs in high dimension
• Navigability of Random Geometric Graphs in the Universe and Other Spacetimes
• On the distances within cliques in a soft random geometric graph
• High Performance Algorithms for Quantum Gravity and Cosmology