Evolution of scale-free random graphs: Potts model formulation

Abstract

We study the bond percolation problem in random graphs of $N$ weighted vertices, where each vertex $i$ has a prescribed weight $P_i$ and an edge can connect vertices $i$ and $j$ with rate $P_i{P}_j$. The problem is solved by the $q\to 1$ limit of the $q$-state Potts model with inhomogeneous interactions for all pairs of spins. We apply this approach to the static model having $P_i\propto i^{-\mu }(0<\mu <1)$ so that the resulting graph is scale-free with the degree exponent $\lambda =1+1/\mu$. The number of loops as well as the giant cluster size and the mean cluster size are obtained in the thermodynamic limit as a function of the edge density, and their associated critical exponents are also obtained. Finite-size scaling behaviors are derived using the largest cluster size in the critical regime, which is calculated from the cluster size distribution, and checked against numerical simulation results. We find that the process of forming the giant cluster is qualitatively different between the cases of $\lambda >3$ and $2<\lambda <3$. While for the former, the giant cluster forms abruptly at the percolation transition, for the latter, however, the formation of the giant cluster is gradual and the mean cluster size for finite $N$ shows double peaks.

34 pages, 9 figures, elsart.cls, final version appeared in NPB

References in corpus (16)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Random graphs with arbitrary degree distributions and their applications
• Evolution of networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Breakdown of the Internet under intentional attack
• Universal Behavior of Load Distribution in Scale-free Networks
• Percolation Critical Exponents in Scale-Free Networks
• A General Formalism for Inhomogeneous Random Graphs
• Statistical ensemble of scale-free random graphs
• Correlated random networks
• Uncorrelated Random Networks
• Principles of statistical mechanics of random networks
• Scale free networks from a Hamiltonian dynamics

Cited by in corpus (47)

• Critical phenomena in complex networks
• Percolation on complex networks: Theory and application
• Percolation Transitions in Scale-Free Networks under Achlioptas Process
• Kuramoto model with frequency-degree correlations on complex networks
• Synchronization transition in scale-free networks: Clusters of synchrony
• Cluster aggregation model for discontinuous percolation transition
• Recent advances of percolation theory in complex networks
• Critical behavior of the relaxation rate, the susceptibility, and a pair correlation function in the Kuramoto model on scale-free networks
• Percolation transition in networks with degree-degree correlation
• Synchronization transition of heterogeneously coupled oscillators on scale-free networks
• Homogeneous complex networks
• Analytic solution of a static scale-free network model
• Spin Glass Phase Transition on Scale-Free Networks
• Intrinsic degree-correlations in static model of scale-free networks
• Load distribution in weighted complex networks
• Universal mechanism for hybrid percolation transitions
• Smeared phase transitions in percolation on real complex networks
• Scaling of nestedness in complex networks
• Maximum flow and topological structure of complex networks
• Broad edge of chaos in strongly heterogeneous Boolean networks
• Correlations in interacting systems with a network topology
• Percolation and Loop Statistics in Complex Networks
• Synchronization in the random field Kuramoto model on complex networks
• Percolation transition in correlated hypergraphs
• Incorporating Heterogeneous Interactions for Ecological Biodiversity
• Understanding the temporal pattern of spreading in heterogeneous networks: Theory of the mean infection time
• Percolation transition and distribution of connected components in generalized random network ensembles
• Impact of noise and damage on collective dynamics of scale-free neuronal networks
• Localization in random bipartite graphs: numerical and empirical study
• Ferromagnetic transition in a simple variant of the Ising model on multiplex networks
• Inverse transitions in a spin-glass model on a scale-free network
• Scaling in local to global condensation of wealth on sparse networks
• Scaling and universality for percolation in random networks: A unified view
• Clustering Algorithms for Scale-free Networks and Applications to Cloud Resource Management
• Organic Design of Massively Distributed Systems: A Complex Networks Perspective
• Giant component in a configuration-model power-law graph with a variable number of links
• A hybrid percolation transition at a finite transition point in scale-free networks
• Degree distributions under general node removal: Power-law or Poisson?
• Finite-size scaling of percolation on scale-free networks
• Percolation transitions with nonlocal constraint
• A program generating homogeneous random graphs with given weights
• Relevance of the minimum degree to dynamic fluctuation in strongly heterogeneous networks
• Spin-glass transition in the Ising model on multiplex networks
• Discontinuous emergence of a giant cluster in assortative scale-free networks
• Nonreciprocal random networks and their percolation properties
• Ground state energy of $q$-state Potts model: the minimum modularity
• Spectral densities of scale-free networks