The small world phenomenon in social networks is quite a surprising property when one first learns of it [wikipedia: small world phenomenon]. Six degrees of separation - the idea that each person is connected to every other person by a path of length 6 on average - is quite remarkable. Yet we observe the small world phenomenon in many different types of networks.

We discussed the web graph in class recently. [1] discusses the structure of the web graph using results from a web crawl of approximately 200 million pages and 1.5 billion links. It describes the graph as consisting of 4 parts: (1) SCC: a giant strongly connected component of pages that can reach each other, (2) IN: pages that can reach SCC but cannot be reached from SCC, (3) OUT: pages that can be reached from SCC but cannot reach SCC, and (4) TENDRILS: pages that can neither reach nor be reached from SCC. Previous work reported that most pairs of webpages are separated by few (<20) links; this can be thought of as a small world phenomenon. [1], however, reports a more subtle picture claiming that over 75% of the time there is no directed path from a random start node to a random finish node.

[2] discusses the notion of “two degrees of separation in complex food webs.” The food web can be thought of as a network where nodes are “trophic species” and species on either end of a link have a consumer-resource (e.g. predator-prey) relationship. The interdependence amongst species in the food web means that perturbations (such as population fluctuations) in one species can have significant effects on other species - the question is how much of the food web is affected by a perturbation to one of the species. Emperical evidence suggests that strong effects rarely propogate more than 3 links away from the initial perturbation. However, [2] finds that there are two degrees of separation even in large complex food webs, i.e., the average shortest path distance between any two species is two. This suggests that a local perturbation can effect almost the entire food web.

References:
[1] Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, Janet Wiener: Graph structure in the web
[2] Richard J. Williams, Eric L. Berlow, Jennifer A. Dunne, Albert-László Barabási, Neo D. Martinez: Two degrees of separation in complex food webs (2002)
[3] S. Strogatz, D. Watts: Nature 393, 440-442 (1998 )
[4] J. Kleinberg: Navigation in a small world; Nature 406 (2000), 845