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

Random geometric graphs (RGGs) 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 RGGs. For any RGG, defined through a rigid or a soft geometric rule, the method reduces to a nontrivial satisfaction problem: Given N nodes, a domain D, and a desired average connectivity 〈k〉, find, if any, the distribution of nodes having support in 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∈[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 antigeometry 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.