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

DOI10.1103/PHYSREVE.91.042136MaRDI QIDQ6256907zbMATH OpenWikidataFDO

Authors Massimo Ostilli, Ginestra Bianconi

Publication date 1 December 2014

Full work available at URL https://doi.org/10.1103/PHYSREVE.91.042136

Mathematics Subject Classification ID

Graph theory (05Cxx) Communication networks in operations research (90B18) Operations research and management science (90Bxx) Education of combinatorics, graph theory, probability theory, and statistics (97Kxx)

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 $mathcalD$, and a desired average connectivity $langlekangle$, find - if any - the distribution of nodes having support in $mathcalD$ and average connectivity $langlekangle$. 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 $mathopO(N)$ jump of $langlekangle$. Other intermediate values of $langlekangle$ correspond to very rare graph realizations. The phase transition is observed as a function of a parameter $ain[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.

This page was built for publication: Statistical mechanics of random geometric graphs: Geometry-induced first order phase transition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6256907)