Random Sequential Renormalization and Agglomerative Percolation in Networks: Application to Erd"os-R'enyi and Scale-free Graphs
arXiv:1109.4631 · doi:10.1103/PhysRevE.84.066111
Abstract
We study the statistical behavior under random sequential renormalization(RSR) of several network models including Erd"os R'enyi (ER) graphs, scale-free networks and an annealed model (AM) 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 [C.Song et.al], 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 laws seen there. For critical trees it happens as N/N0 -> 0 in the limit of large systems (where N0 is the initial size of the graph and N its size at a given RSR step). In contrast, it happens at finite N/N0 in sparse ER graphs and in the annealed model, while it happens for N/N0 -> 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 star-like structure in agreement with the results of Radicchi et. al. 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.
References in corpus (20)
- Emergence of scaling in random networks
- The structure and function of complex networks
- Random graphs with arbitrary degree distributions and their applications
- Epidemic dynamics and endemic states in complex networks
- Self-similarity of complex networks
- Origins of fractality in the growth of complex networks
- A fast Monte Carlo algorithm for site or bond percolation
- Efficient Monte Carlo algorithm and high-precision results for percolation
- How to calculate the fractal dimension of a complex network: the box covering algorithm
- Skeleton and fractal scaling in complex networks
- 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
- Self-similar Scale-free Networks and Disassortativity
- Complex networks renormalization: flows and fixed points
- The Largest Cluster in Subcritical Percolation
- Renormalization flows in complex networks
- Random Sequential Renormalization of Networks I: Application to Critical Trees
- Irreversible Aggregation and Network Renormalization
- Exact solutions for mass-dependent irreversible aggregations
Cited by in corpus (6)
- Recent advances and open challenges in percolation
- Percolation transitions in the survival of interdependent agents on multiplex networks, catastrophic cascades, and SOS
- Dynamics and Processing in Finite Self-Similar Networks
- Agglomerative Percolation on Bipartite Networks: A Novel Type of Spontaneous Symmetry Breaking
- Alternative criterion for two-dimensional wrapping percolation
- Random growth lattice filling model of percolation: a crossover from continuous to discontinuous transition