Small World Exercise

Small world networks were inspired by the sociological phenomenon of "six degrees of separation": the network of human friendships is thought to link random pairs of humans through a remarkably small number of first-name basis relationships (you know someone who knows someone who ... who knows someone who was struck by a meteor, just like the dinosaurs). This simple model has been studied perhaps too thoroughly, but remains a nice introduction both to random network construction, to breadth-first search algorithms, and to scaling collapses. Your resulting software can then also be applied to real-world networks.

References

Duncan Watts and Steven Strogatz, Collective Dynamics of "small world" Networks
Mark Newman, The structure and function of complex networks
Mark Newman, Models of the Small World
Mark Newman, Scientific collaboration networks II: shortest paths, weighted networks, and centrality.
Mark Newman and Duncan Watts, Renormalization--group analysis of the small world network model
Michelle Girvan and Mark Newman, Community structure in social and biological networks
Yook, Oltvai, and Barabasi, Comparing Different Protein Interaction Networks

Links

James P. Sethna, Christopher R. Myers.

Last modified: August 24, 2006

Statistical Mechanics: Entropy, Order Parameters, and Complexity, now available at Oxford University Press (USA, Europe).