Sunday, January 09, 2005

Spatial networks and 'small world' theory

In reading the history of nations, we find that, like individuals,they have their whims and their peculiarities; their seasons of excitement and recklessness, when they care not what they do. We find that whole communities suddenly fix their minds upon one object, and go mad in its pursuit; that millions of people become simultaneously impressed with one delusion, and run after it, till their attention is caught by some new folly more captivating than the first. We see one nation suddenly seized, from its highest to its lowest members, with a
fierce desire of military glory; another as suddenly becoming crazed upon a religious scruple, and neither of them recovering its senses until it has shed rivers of blood and sowed a harvest of groans and tears

Charles Mackay, 1841, "Memoirs of popular delusions"
 The opening paragraph of Charles Mackay's work poses the central question that is at the heart of the 'small world theory' of networks. The mechanics of the 'madness' that Mackay describes are also the mechanics of the coherence of fireflies and crickets all chirping at random to produce a single pattern.

Doug Simpson's review of "Six Degrees:The Science of a connected age" by Duncan Watts provides a concise overview and introduction to the scope of this aspect of network theory.

Ahmed Helmy has taken network theory and applied it to geographic(spatial) graphs such as radio networks which provides for some really interesting practical consequences of utilizing network theory to develop mobile ad hoc radio networks. In an interview for Technology Research News he describes how the introduction of a small number of random links can greatly reduce the path length of messages in these networks. Radio networks are much more highly clustered and limited by distance and energy constraints than informatinal networks traditionally studied in 'small world' theory. As such they represent a more realistic model of economic networks.

In his original paper(.pdf) he shows how geographic networks can be transformed into small networks by the presence of a limited number(0.2 - 20%) of random links with a median distance of 20-40% of the network diameter.

Consider the grid of streets comprising the centre of Melbourne(say) - if there are 10 by 10 streets, then a random single link (1%) stretching across 3 blocks will turn this into a 'small world' network! Interestingly this is almost precisely the size of the network of arcades and plazas that connect the central area of Melbourne (Bourke and Swanston Street to Flinders and Elizabeth Street)
Return to Kiangardarup


Post a Comment

<< Home