Stochastically Evolving Networks
Studies of random walks and related processes in random environments have largely concentrated on periodic lattices with quenched structural disorder, and especially one-dimensional systems, although there has also been work on transport processes in networks generated by random tessellations and in random continua. Recent interest in communications networks, and especially in the world-wide web, raises the need to study processes defined on radically different network structures. Models of special interest are those that are 'scale-free' (that is, with heavy-tailed coordination number distributions) or possess the 'small-world' property (most vertex pairs are only a few links apart).
I discuss a class of models in which the structure of a network evolves with time that may be of interest as the random substrates on which transport processes take place. These models include both random trees and random networks with cross-links. The evolution of the properties of these networks, both as functions of time, and as functions of the number of sites present, is explored using simulation, exact calculations, and arguments of mean-field type. The work described extends previous studies in which time-evolving processes produce heavy-tailed distributions through the competition of random growth and random age, applicable in a wide variety of contexts.
This presentation is based on collaborative work with D.Y.C. Chan and A.S. Leong (University of Melbourne) and W.J. Reed (University of Victoria, Canada).