Quasistatic scale-free networks

Network rewiring dynamics with convergence towards a star network

Network rewiring as a method for producing a range of structures was first introduced in 1998 by Watts & Strogatz (Nature393, 440-442. (doi:10.1038/30918)). This approach allowed a transition from regular through small-world to a random network. The subsequent interest in scale-free networks motivated a number of methods for developing rewiring approaches that converged to scale-free networks. This paper presents a rewiring algorithm (RtoS) for undirected, non-degenerate, fixed size networks that transitions from regular, through small-world and scale-free to star-like networks. Applications of the approach to models for the spread of infectious disease and fixation time for a simple genetics model are used to demonstrate the efficacy and application of the approach.

How scale-free networks and large-scale collective cooperation emerge in complex homogeneous social systems

We study how heterogeneous degree distributions and large-scale collective cooperation in social networks emerge in complex homogeneous systems by a simple local rule: learning from the best in both strategy selections and linking choices. The prisoner's dilemma game is used as the local dynamics. We show that the social structure may evolve into single-scale, broad-scale, and scale-free (SF) degree distributions for different control parameters. In particular, in a relatively strong-selfish parameter region the SF property can be self-organized in social networks by dynamic evolutions and these SF structures help the whole node community to reach a high level of cooperation under the poor condition of a high selfish intention of individuals.

Self-organized scale-free networks

Growth and preferential attachments have been coined as the two fundamental mechanisms responsible for the scale-free feature in complex networks, as characterized by an algebraic degree distribution. There are situations, particularly in biological networks, where growth is absent or not important, yet some of these networks still exhibit the scale-free feature with a small degree exponent. Here we propose two classes of models to account for this phenomenon. We show analytically and numerically that, in the first model, a spectrum of algebraic degree distributions with a small exponent can be generated. The second model incorporates weights for nodes, and it is able to generate robust scale-free degree distribution with larger algebraic exponents. Our results imply that it is natural for a complex network to self-organize itself into a scale-free state without growth.

Statistical mechanics of topological phase transitions in networks

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= summation operator (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)+alpha)ln(k(i)), the transition is continuous, and at the critical temperature scale-free graphs can be recovered. Finally, by abruptly decreasing the temperature, nonequilibrium processes (e.g., nucleation and growth of particular topological phases) can also be interpreted by the present approach.

Diffusion-limited friendship network: a model for six degrees of separation

A dynamic model of a society is studied where each person is an uncorrelated and noninteracting random walker. A dynamical random graph represents the acquaintance network of the society whose nodes are the individuals and links are the pairs of mutual friendships. This network exhibits a different percolationlike phase transition in all dimensions. On introducing simultaneous death and birth rates in the population, we show that the friendship network shows the six degrees of separation for ever after where the precise value of the network diameter depends on the death/birth rate. A susceptible-infected-susceptible-type model of disease spreading shows that this society always remains healthy if the population density is less than certain threshold value.

Scale-free networks from a Hamiltonian dynamics

Contrary to many recent models of growing networks, we present a model with fixed number of nodes and links, where a dynamics favoring the formation of links between nodes with degree of connectivity as different as possible is introduced. By applying a local rewiring move, the network reaches equilibrium states assuming broad degree distributions, which have a power-law form in an intermediate range of the parameters used. Interestingly, in the same range we find nontrivial hierarchical clustering.