Bizhani Golnoosh, Grassberger Peter, Paczuski Maya
Complexity Science Group, University of Calgary, Calgary, Canada T2N 1N4.
Phys Rev E Stat Nonlin Soft Matter Phys. 2011 Dec;84(6 Pt 2):066111. doi: 10.1103/PhysRevE.84.066111. Epub 2011 Dec 15.
We study the statistical behavior under random sequential renormalization (RSR) of several network models including Erdös-Rényi (ER) graphs, scale-free networks, and an annealed model related to ER graphs. In RSR the network is locally coarse grained by choosing at each renormalization step a node at random and joining it to all its neighbors. Compared to previous (quasi-)parallel renormalization methods [Song et al., Nature (London) 433, 392 (2005)], RSR allows a more fine-grained analysis of the renormalization group (RG) flow and unravels new features that were not discussed in the previous analyses. In particular, we find that all networks exhibit a second-order transition in their RG flow. This phase transition is associated with the emergence of a giant hub and can be viewed as a new variant of percolation, called agglomerative percolation. We claim that this transition exists also in previous graph renormalization schemes and explains some of the scaling behavior seen there. For critical trees it happens as N/N(0) → 0 in the limit of large systems (where N(0) is the initial size of the graph and N its size at a given RSR step). In contrast, it happens at finite N/N(0) in sparse ER graphs and in the annealed model, while it happens for N/N(0) → 1 on scale-free networks. Critical exponents seem to depend on the type of the graph but not on the average degree and obey usual scaling relations for percolation phenomena. For the annealed model they agree with the exponents obtained from a mean-field theory. At late times, the networks exhibit a starlike structure in agreement with the results of Radicchi et al. [Phys. Rev. Lett. 101, 148701 (2008)]. While degree distributions are of main interest when regarding the scheme as network renormalization, mass distributions (which are more relevant when considering "supernodes" as clusters) are much easier to study using the fast Newman-Ziff algorithm for percolation, allowing us to obtain very high statistics.
我们研究了几种网络模型在随机顺序重整化（RSR）下的统计行为，这些模型包括厄多斯 - 雷尼（ER）图、无标度网络以及与ER图相关的一种退火模型。在RSR中，网络通过在每个重整化步骤随机选择一个节点并将其与所有邻居相连来进行局部粗粒化。与先前的（准）并行重整化方法[宋等人，《自然》（伦敦）433, 392（2005）]相比，RSR允许对重整化群（RG）流进行更精细的分析，并揭示了先前分析中未讨论的新特征。特别是，我们发现所有网络在其RG流中都表现出二阶相变。这种相变与一个巨型枢纽的出现相关，并且可以被视为渗流的一种新变体，称为聚集渗流。我们声称这种相变在先前的图重整化方案中也存在，并解释了在那里看到的一些标度行为。对于临界树，在大系统的极限情况下（其中N(0)是图的初始大小，N是在给定RSR步骤时它的大小），当N/N(0)→0时会发生这种情况。相比之下，在稀疏ER图和退火模型中，它在有限的N/N(0)时发生，而在无标度网络上，当N/N(0)→1时发生。临界指数似乎取决于图的类型，而不取决于平均度，并且服从渗流现象的通常标度关系。对于退火模型，它们与从平均场理论获得的指数一致。在后期，网络呈现出星状结构，这与拉迪奇等人的结果[《物理评论快报》101, 148701（2008）]一致。虽然当将该方案视为网络重整化时，度分布是主要关注的对象，但质量分布（在将“超节点”视为簇时更相关）使用用于渗流的快速纽曼 - 齐夫算法进行研究要容易得多，这使我们能够获得非常高的统计数据。
