Network evolution by different rewiring schemes

Abstract

Many real world networks, such as social networks, are characterized by rearrangements of the links between nodes (rewiring). Indeed, very few natural networks are static in time, and it is therefore important to study the properties of networks in which rewiring occurs. In this paper, two different rewiring schemes are formulated and compared using a general ordinary differential equation (ODE) model. The equilibrium distributions are analytically derived. It is found that by uniformly choosing a node and a link connected to it, rewiring from different ends of the link yields different equilibrium degree distributions. Rewiring from the neighbor generally produces more high degree nodes. The equilibrium distributions of the ODE model are compared with simulation results of the corresponding stochastic process for rewiring. Conditions are discussed under which our ODE provides a good approximation for the mean of the corresponding stochastic process. © 2008 Elsevier B.V. All rights reserved.