Network Rewiring and related problems

With Doug Plato and more recently Tevong You, I have been looking at exact solutions for network rewiring problems. There are numerous models of statistical physics which are related to network rewiring including: Urn models, Backgammon model, Balls-in-Boxes model, zero range processes, Voter models and Minority games. These models have been applied in the literature to a wide range of applications: cultural transmission including baby name popularity and choice of dog breeds (see for example work of Alex Bentley and colleagues), family name frequency, gene frequencies, glasses, wealth distributions, and language distributions.

We have first provided the correct master equation for the model and then an exact solution for the equation. Our solution gives the exact degree distribution for arbitrary parameters, including finite sized graphs, at any time. This in turn allows us to follow a phase transition in a network in real time. One example network would be the degree-distribution of a Watts-Strogatz model in which edges are rewired randomly (they were originally rewired sequentially). Note that this disproves early suggestions that power-laws in the degree distributions of graphs might be linked to growing networks.

Sketch of the rewiring of a bipartite network or graph representing the cultural transmission of artifacts between individuals through copying and random innovations. The average diameter and distance for the undirected graph obtained using a Molloy-Reed projection from the bipartite to a random unipartite graph. Same again but now including the size of the GCC and the ratio of the second to the first moment minus one (defined to be z) (additional picture)

See the following for more information: