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:

• A Simple Model of Copying and Innovation submission to ECCS08.
• Are Copying and Innovation Enough? Talk given by Doug Plato at ECMI08, 4th July 2008.
  Contribution to proceedings arXiv:0809.2568 with Plato and You.
• Are Copying and Innovation Enough? Talk given to the Brunel University Complexity Community, 25th October 2007. Pulls together elements from both network rewiring and random walks for growing networks work.
• Randomness and Complexity in Networks talk given at the workshop on "Stochastic Networks and Internet Technology", Centro di Ricerca Matematica Ennio De Giorgi, Matematica nelle Scienze Naturali e Sociali, Pisa, 17th - 21st September 2007. To appear in a book edited by the Scuola Normale Superiore. [Proceedings version is at arXiv:0711.0603]
• The Randomness and Complexity in Networks talk I gave at ECCS07 Dresden 2nd October, 2007. The version for the proceedings is Network Rewiring Models [Networks and Heterogeneous Media 3 (2008) 221 arXiv:0707.3783].
• The Cultural Transmission and Network Rewiring Talk I gave at the Laboratory of Computational Engineering of the Helsinki University of Technology, 31st Aug 2007.
• The Network Rewiring talk I gave at CABDyN at Oxford in May 2007, based on the ECCS07 proceedings.
• Exact Solution for the Time Evolution of Network Rewiring Models [Phys.Rev.E. 75 (2007) 056101 cond-mat/0612214]
• The network rewiring talk I gave at ECCS06. The paper produced for the proceedings is Exact Solutions for Models of Cultural Transmission and Network Rewiring [physics/0608052].
• Exact Solutions for Network Rewiring Models [Eur.Phys.J. B 56 (2007) 65-69 cond-mat/0607196]