%0 Journal Article %1 Bizhani2011Random %A Bizhani, Golnoosh %A Sood, Vishal %A Paczuski, Maya %A Grassberger, Peter %D 2011 %I American Physical Society %J Physical Review E %K renormalization, critical-phenomena networks tree-graphs %N 3 %P 036110+ %R 10.1103/physreve.83.036110 %T Random sequential renormalization of networks: Application to critical trees %U http://dx.doi.org/10.1103/physreve.83.036110 %V 83 %X We introduce the concept of random sequential renormalization (RSR) for arbitrary networks. RSR is a graph renormalization procedure that locally aggregates nodes to produce a coarse grained network. It is analogous to the (quasi)parallel renormalization schemes introduced by C. Song et al. C. Song et al., Nature (London) 433, 392 (2005) and studied by F. Radicchi et al. F. Radicchi et al., Phys. Rev. Lett. 101, 148701 (2008), but much simpler and easier to implement. Here we apply RSR to critical trees and derive analytical results consistent with numerical simulations. Critical trees exhibit three regimes in their evolution under RSR. (i) For N0ν≲N<N0, where N is the number of nodes at some step in the renormalization and N0 is the initial size of the tree, RSR is described by a mean-field theory, and fluctuations from one realization to another are small. The exponent ν=1/2 is derived using random walk and other arguments. The degree distribution becomes broader under successive steps, reaching a power law pk\~1/kγ with γ=2 and a variance that diverges as N01/2 at the end of this regime. Both of these latter results are obtained from a scaling theory. (ii) For N0νstar≲N≲N01/2, with νstar≈1/4 hubs develop, and fluctuations between different realizations of the RSR are large. Trees are short and fat with an average radius that is O(1). Crossover functions exhibiting finite-size scaling in the critical region NÑ01/2→∞ connect the behaviors in the first two regimes. (iii) For N≲N0νstar, star configurations appear with a central hub surrounded by many leaves. The distribution of stars is broadly distributed over this range. The scaling behaviors found under RSR are identified with a continuous transition in a process called ” agglomerative percolation” (AP), with the coarse-grained nodes in RSR corresponding to clusters in AP that grow by simultaneously attaching to all their neighboring clusters.

@article{Bizhani2011Random, abstract = {{We introduce the concept of random sequential renormalization (RSR) for arbitrary networks. RSR is a graph renormalization procedure that locally aggregates nodes to produce a coarse grained network. It is analogous to the (quasi)parallel renormalization schemes introduced by C. Song et al. [C. Song et al., Nature (London) 433, 392 (2005)] and studied by F. Radicchi et al. [F. Radicchi et al., Phys. Rev. Lett. 101, 148701 (2008)], but much simpler and easier to implement. Here we apply RSR to critical trees and derive analytical results consistent with numerical simulations. Critical trees exhibit three regimes in their evolution under RSR. (i) For N0ν≲N<N0, where N is the number of nodes at some step in the renormalization and N0 is the initial size of the tree, RSR is described by a mean-field theory, and fluctuations from one realization to another are small. The exponent ν=1/2 is derived using random walk and other arguments. The degree distribution becomes broader under successive steps, reaching a power law pk\~{}1/kγ with γ=2 and a variance that diverges as N01/2 at the end of this regime. Both of these latter results are obtained from a scaling theory. (ii) For N0νstar≲N≲N01/2, with νstar≈1/4 hubs develop, and fluctuations between different realizations of the RSR are large. Trees are short and fat with an average radius that is O(1). Crossover functions exhibiting finite-size scaling in the critical region N\~{}N01/2→∞ connect the behaviors in the first two regimes. (iii) For N≲N0νstar, star configurations appear with a central hub surrounded by many leaves. The distribution of stars is broadly distributed over this range. The scaling behaviors found under RSR are identified with a continuous transition in a process called ” agglomerative percolation” (AP), with the coarse-grained nodes in RSR corresponding to clusters in AP that grow by simultaneously attaching to all their neighboring clusters.}}, added-at = {2019-06-10T14:53:09.000+0200}, author = {Bizhani, Golnoosh and Sood, Vishal and Paczuski, Maya and Grassberger, Peter}, biburl = {https://www.bibsonomy.org/bibtex/26e9f3bb406c3b2ffebe721e2bb8b7a69/nonancourt}, citeulike-article-id = {9048689}, citeulike-linkout-0 = {http://dx.doi.org/10.1103/physreve.83.036110}, citeulike-linkout-1 = {http://link.aps.org/abstract/PRE/v83/i3/e036110}, citeulike-linkout-2 = {http://link.aps.org/pdf/PRE/v83/i3/e036110}, doi = {10.1103/physreve.83.036110}, interhash = {3264ff057a89e26ee1f169c6c4c2575f}, intrahash = {6e9f3bb406c3b2ffebe721e2bb8b7a69}, journal = {Physical Review E}, keywords = {renormalization, critical-phenomena networks tree-graphs}, month = mar, number = 3, pages = {036110+}, posted-at = {2011-03-23 10:50:06}, priority = {2}, publisher = {American Physical Society}, timestamp = {2019-08-01T16:07:48.000+0200}, title = {{Random sequential renormalization of networks: Application to critical trees}}, url = {http://dx.doi.org/10.1103/physreve.83.036110}, volume = 83, year = 2011 }