Random Sequential Renormalization of Networks I: Application to Critical Trees

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 {\it et al.} (Nature {\bf 433}, 392 (2005)) and studied more recently by F. Radicchi {\it et al.} (Phys. Rev. Lett. {\bf 101}, 148701 (2008)), but much simpler and easier to implement. In this first paper 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) An initial regime $N_0^{\nu }\lesssim N<N_0$, where $N$ is the number of nodes at some step in the renormalization and $N_0$ is the initial size. RSR in this regime is described by a mean field theory and fluctuations from one realization to another are small. The exponent $\nu =1/2$ is derived using random walk arguments. The degree distribution becomes broader under successive renormalization -- reaching a power law, $p_k\sim 1/k^{\gamma }$ with $\gamma =2$ and a variance that diverges as $N_0^{1/2}$ at the end of this regime. Both of these results are derived based on a scaling theory. (ii) An intermediate regime for $N_0^{1/4}\lesssim N\lesssim N_0^{1/2}$, in which hubs develop, and fluctuations between different realizations of the RSR are large. Crossover functions exhibiting finite size scaling, in the critical region $N\sim N_0^{1/2}\to \infty$, connect the behaviors in the first two regimes. (iii) The last regime, for $1\ll N\lesssim N_0^{1/4}$, is characterized by the appearance of star configurations with a central hub surrounded by many leaves. The distribution of sizes where stars first form is found numerically to be a power law up to a cutoff that scales as $N_0^{{\nu }_{star}}$ with ${\nu }_{star}\approx 1/4$.

References in corpus (14)

• Emergence of scaling in random networks
• The structure and function of complex networks
• Random graphs with arbitrary degree distributions and their applications
• The spread of epidemic disease on networks
• Nonequilibrium Critical Phenomena and Phase Transitions into Absorbing States
• Epidemic dynamics and endemic states in complex networks
• Self-similarity of complex networks
• Origins of fractality in the growth of complex networks
• How to calculate the fractal dimension of a complex network: the box covering algorithm
• Small world-Fractal Transition in Complex Networks: Renormalization Group Approach
• Fractality in complex networks: critical and supercritical skeletons
• A box-covering algorithm for fractal scaling in scale-free networks
• Complex networks renormalization: flows and fixed points
• Renormalization flows in complex networks

Cited by in corpus (9)

• Recent advances and open challenges in percolation
• Self-similar scaling of density in complex real-world networks
• The evolutionary dynamics of protein-protein interaction networks inferred from the reconstruction of ancient networks
• On the Hyperbolicity of Large-Scale Networks
• Dynamics and Processing in Finite Self-Similar Networks
• Irreversible Aggregation and Network Renormalization
• Agglomerative Percolation on Bipartite Networks: A Novel Type of Spontaneous Symmetry Breaking
• Random Sequential Renormalization and Agglomerative Percolation in Networks: Application to Erd"os-R'enyi and Scale-free Graphs
• Exact solutions for mass-dependent irreversible aggregations