Statistical mechanics of topological phase transitions in networks

Abstract

We provide a phenomenological theory for topological transitions in restructuring networks. In this statistical mechanical approach energy is assigned to the different network topologies and temperature is used as a quantity referring to the level of noise during the rewiring of the edges. The associated microscopic dynamics satisfies the detailed balance condition and is equivalent to a lattice gas model on the edge-dual graph of a fully connected network. In our studies -- based on an exact enumeration method, Monte-Carlo simulations, and theoretical considerations -- we find a rich variety of topological phase transitions when the temperature is varied. These transitions signal singular changes in the essential features of the global structure of the network. Depending on the energy function chosen, the observed transitions can be best monitored using the order parameters Phi_s=s_{max}/M, i.e., the size of the largest connected component divided by the number of edges, or Phi_k=k_{max}/M, the largest degree in the network divided by the number of edges. If, for example the energy is chosen to be E=-s_{max}, the observed transition is analogous to the percolation phase transition of random graphs. For this choice of the energy, the phase-diagram in the [<k>,T] plane is constructed. Single vertex energies of the form E=sum_i f(k_i), where k_i is the degree of vertex i, are also studied. Depending on the form of f(k_i), first order and continuous phase transitions can be observed. In case of f(k_i)=-(k_i+c)ln(k_i), the transition is continuous, and at the critical temperature scale-free graphs can be recovered.

12 pages, 12 figures, minor changes, added a new refernce, to appear in PRE

References in corpus (3)

• The structure and function of complex networks
• Scale free networks from a Hamiltonian dynamics
• Topological phase transitions of random networks

Cited by in corpus (37)

• Critical phenomena in complex networks
• Structure and dynamics of molecular networks: A novel paradigm of drug discovery. A comprehensive review
• The statistical mechanics of networks
• Maximal planar networks with large clustering coefficient and power-law degree distribution
• Learning and innovative elements of strategy adoption rules expand cooperative network topologies
• Solution of the 2-star model of a network
• Majority-vote model on random graphs
• Entropy of stochastic blockmodel ensembles
• Solution for the properties of a clustered network
• Subgraphs and network motifs in geometric networks
• Percolation transition in networks with degree-degree correlation
• Nonextensive aspects of self-organized scale-free gas-like networks
• A statistical mechanics approach for scale-free networks and finite-scale networks
• Does the brain behave like a (complex) network? I. Dynamics
• Unified model for network dynamics exhibiting nonextensive statistics
• The Grand Canonical ensemble of weighted networks
• The Social Climbing Game
• Ageing as a price of cooperation and complexity: Self-organization of complex systems causes the ageing of constituent networks
• Phase transitions in social networks
• Fluctuation-dissipation relations for complex networks
• Percolation on correlated random networks
• Organization of networks with tagged nodes and biased links: a priori distinct communities. The case of Intelligent Design Proponents and Darwinian Evolution Defenders
• Statistical mechanics of scale-free networks at a critical point: Complexity without irreversibility?
• Functional-Friction Networks: New Insights on the Laboratory Earthquakes
• Phase transitions on Markovian bipartite graphs - an application of the zero-range process
• Statistical mechanics of coevolving spin system
• Condensation of degrees emerging through a first-order phase transition in classical random graphs
• Scale-freeness for networks as a degenerate ground state: A Hamiltonian formulation
• Analytic solution of the two-star model with correlated degrees
• Ageing of complex networks
• Generalised thresholding of hidden variable network models with scale-free property
• Reverse engineering of linking preferences from network restructuring
• Construction of equilibrium networks with an energy function
• Tsallis mapping in growing complex networks with fitness
• Phase transitions in atypical systems induced by a condensation transition on graphs
• Free-energy density functional for Strauss's model of transitive networks
• Birth-Burst in Evolving Networks