Random sequential renormalization of networks: Application to critical trees

TY - JOUR

T1 - Random sequential renormalization of networks

T2 - Application to critical trees

AU - Bizhani, G.

AU - Vishal, Sood

AU - Paczuski, Maya

AU - Grassberger, Peter

PY - 2011/3/22

Y1 - 2011/3/22

N2 - 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 and studied by F. Radicchi, 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νstarNN01/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 NN0ν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.

AB - 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 and studied by F. Radicchi, 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νstarNN01/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 NN0ν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.

U2 - 10.1103/PhysRevE.83.036110

DO - 10.1103/PhysRevE.83.036110

M3 - Journal article

SN - 2470-0045

VL - 83

SP - 036110

JO - Physical Review E

JF - Physical Review E

IS - 3

ER -