UK Nonlinear News, August 2002


Small Worlds: The Dynamics of Networks Between Order and Disorder

D.J. Watts

Reviewed by Jaroslav Stark

Princeton University Press, 1999
ISBN 0691005419
Hardback, #29.95 (Amazon), 278 pages

In one form or another the "small worlds" concept has been around for a long time. Informally, in the context of social interactions it refers to the idea that if you pick any two people at random there is a good chance that they are connected by a short path of mutual acquaintances. This has been highlighted by phrases such as "six degrees of separation" that have entered the common vocabulary. A play and its movie adaptation popularised this term a decade ago. Most mathematicians will be familiar with the concept of Erdos number which is the number of steps of joint authorship required to connect oneself to Paul Erdos. Thus Erdos himself has an Erdos number of 0, anyone who has co-authored a paper with him has Erdos number 1, any co-authors of those with Erdos number 1 have Erdos number 2 and so on. For many years it was informally believed that most working mathematicians would have a very low Erdos number. With the advent of computerised bibliographies this is increasingly being confirmed (see http://www.oakland.edu/~grossman/erdoshp.html) with the average Erdos number being 4.69... (restricted to those who have a finite Erdos number, which encompasses the vast majority of mathematicians). A similar experiment has been carried out for movie actors, who are deemed to be connected if they have appeared in the same film. This network has been somewhat whimsically centred on a rather obscure actor called Kevin Bacon ( http://www.cs.virginia.edu/oracle). Despite his relative lack of fame, the average Bacon number is a mere 2.9, only slightly worse than the 2.6 for the "most connected" actor, who is currently Christopher Lee.

Such calculations, whilst entertaining, also serve a more serious purpose in social sciences research for those trying to understand the structure of social communities. Research of both a theoretical and experimental nature has been underway at least since the 1960's. The most famous example is probably the experiments of Milgram who asked volunteers to try and deliver packets to a specific recipient in another part of the country. Senders were only allowed to post packets to someone whom they knew by first name, and these recipients in turned passed on the packages under the same rules. The object was to get the packet from source to target with as few links as possible. Milgram found that the median number of links was around 5, despite the fact that at each stage senders could only select what they thought was the next best link, rather that being able to optimise a route with full knowledge of the acquaintance graph.

Research on networks with such properties has carried on in a number of disparate disciplines for many years. Some five years ago however, there was a dramatic surge of interest in this field, which coincided with the realization that similar ideas may have relevance to a very wide variety of applications, ranging from telecommunications networks (including the Internet) to networks of protein interactions within and between cells. At the same time there was an increase in the level of mathematical analysis of graphs of this kind and an attempt to make more use of concepts from the well established subject of random graph theory. At least in part, the increase in popularity of this field is due to the author of this book and his PhD supervisor at the time, Steve Strogatz.

The book is divided into two main sections. The first deals with the structure of small world graphs, and lays down some of the basic terminology and theory. It develops a number of ways of constructing such graphs, and then defines various ways of characterising their properties. It presents what little theoretical understanding we have of these and then describes three real examples: the Kevin Bacon network alluded to above, the electricity distribution grid in the western USA and the neural network in the nematode worm Caenorhabditis Elegans (which is a paradigm organism in many branches of experimental biology). The second section of the book is in many ways more interesting in that it discusses the behaviour of dynamical systems living on small world networks. This includes models of disease spread (which is a very realistic application, since infection often largely depends on social interactions), simple cellular automata, game theory models such as the Prisoner's Dilemma and coupled oscillators. Each of these is dealt with relatively briefly, and only preliminary conclusions are drawn. This is inevitable since this is such a young subject, and many of the problems mentioned are at the cutting edge of research. However, there is certainly enough here to convince the reader that there is a great range of interesting phenomena in this field and to motivate them to begin research on some of these problems.

Overall, therefore,e this is an interesting book in a subject that is rapidly growing and that is creating interest in a wide range of application disciplines. Until recently, it was the only book in the field. Within the last few months however, two new volumes have appeared: Linked: The New Science of Networks by A-L Barabasi and Small World: Uncovering Nature's Hidden Networks by Mark Buchanan. We hope to bring you a review of these in the near future.

UK Nonlinear News thanks Princeton University Press for providing a review copy of this book.

A listing of books reviewed in UK Nonlinear News is available.


<< Move to UK Nonlinear News Issue 29 Index Page.
Page Created: 5 August 2002.
Last Updated: 5 August 2002.
uknonl@amsta.leeds.ac.uk