18 - Evolving networks and the Worldwide Web

Summary

In Chapters 2, 4 and 7–9 we considered the evolution of a network towards optimality by, essentially, following the steepest-descent path of a prescribed criterion function, even if sometimes this calculation took a simple and intuitive form. However, one generally thinks of ‘evolution’ as something much less premeditated, in which some simple and plausible response rule induces structural changes in the system, whose effect and whose effective guiding principle (if any) become evident only with time. In the case of Darwinian evolution, the effective guiding principle is that of survival. The degree of sophistication induced by this stark criterion still lies beyond our full comprehension, and is comparable in scale only to the time and tirelessness of trial needed to achieve it.

Interest in these matters is demonstrated by the growing literature on evolving automata, artificial neural networks and the like. However, the Worldwide Web now presents an example, if simple, of spontaneous evolution in a technological context.

Random graphs and the Web

Real-life response rules will in general be local, in that a change is induced in some part of the system in response to stimuli or information manifest in that part. The execution of the rule and the information on which it is based will also show natural variability, i.e. be ‘random’. In the case of networks we are thus considering the generation of a random graph from local rules, and are interested to see whether the network thus generated can be seen as a statistical solution to an implied optimisation problem, and what its character may be.

There is now a large literature on random graphs.