Statistical mechanics of random geometric graphs: Geometry-induced first-order phase transition
Statistical mechanics of random geometric graphs: Geometry-induced first-order phase transition
复制标题
DOI：
10.1103/physreve.91.042136
复制
发表时间：
2015-04-27
影响因子：
2.4
通讯作者：
Bianconi, Ginestra
中科院分区：
文献类型：
--
作者：
Ostilli, Massimo;Bianconi, Ginestra
随机几何图可以形式化为隐变量模型，其中隐变量是节点的坐标。在这里，我们开发了一种通用的方法来提取一个通用的隐变量模型的典型配置，并将所得方程应用到RGG。对于任何通过刚性或柔性几何规则定义的RGG，该方法简化为一个非平凡的满足问题：给定N个节点，一个域D和一个期望的平均连通度（k），找到（如果有的话）在D和平均连通度（k）中具有支持度的节点的分布。我们发现，在热力学极限下，节点要么均匀分布，要么在一个小区域内高度凝聚，这两个区域被一级相变分开，其特征是O（N）跳跃（k）。（k）的其他中间值对应于非常罕见的图实现。观察到的相变作为一个参数的函数，调整底层的几何形状。特别地，a = 1表示仅连接近节点的刚性几何，而a = 0表示仅连接远节点的刚性反几何。当a = 1/2时，没有几何形状，也没有相变。在讨论了数值分析后，我们提供了一个组合的论点，充分解释了机制诱导这种相变，并认识到它是一个容易-难-容易的转变。我们的研究结果表明，在一般情况下，ad hoc优化网络很难设计，除非依赖于特定的异构结构，不一定是无标度的。
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 epsilon [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.