It’s a Small World After All

NOTE: This post originally appeared on Scientific American’s blog network on June 28, 2012.


Conventional wisdom states that it’s all about who you know, although conventional wisdom is typically vague on pesky details like actual mechanisms. Perhaps that’s why there is so much scientific interest these days in studying the intricacies of social networks, particularly organizational patterns.
I share far more social contacts with the Time Lord, for instance, than with anyone else, as one might expect with a spouse, and the overlap is particularly noticeable on Facebook. But I also have select friends and acquaintances outside my usual circles. Because of this, the likelihood that, at some point, we will uncover a surprising mutual connection is very high indeed. It’s a network thing. When it comes to social circles, it really is a small, small world. Literally.
The small world phenomenon is better known to most of us as “six degrees of separation,” and epitomized by the popular game “Six Degrees of Kevin Bacon,” in which players try to make a series of connections to the actor based on those who have been associated in some way with his movies.
In the original 1967 study by psychologist Stanley Milgram, information packets were sent to randomly selected people in Omaha, Nebraska, and Wichita, Kansas, containing a letter describing the purpose of the experiment, and providing basic information about the target contact in Boston, Massachusetts, asking them to forward an enclosed letter. If the recipient knew the target, s/he would forward the letter directly. If not, s/he would forward it to a friend or relative more likely to know the target. While the number of connections it took for the letters to reach the target varied, the average was around 5.5 – hence, “six degrees of separation.”
Sure, there were “issues” with Milgram’s experiment, eg, his conclusions were based on a minuscule data sample. In one experiment, out of 60 letters, 50 people responded to his challenge to forward the letter via their social network, but only three letters eventually reached their destination. A far greater number of people didn’t bother to participate in the experiment at all.
That said, the study does offer intriguing evidence that smaller communities, such as actors and mathematicians are densely connected by chains of personal or professional associations. (What’s your Erdos number?” in honor of mathematician Paul Erdos, replaces “What’s your sign?” as the pick up line of choice in math and science departments. Erdos is the Kevin Bacon of mathematics.)

Which one of these pretty colored dots represents Kevin Bacon?

If that’s the case, then there must be some advantage to a small world type of network, in order for it to be so prevalent. Fast forward to 1998, when a paper appeared by Duncan Watts and Steven Strogatz (he’s on Twitter!) detailing a simple lattice network model (a regular network as opposed to a random network) they devised on the computer.
The network was “highly clustered” — that is, each individual node was connected to each of its four nearest neighbors, by either a line or an edge.
So there were many, many short-range connections, which might be all well and good for the little nodal clusters who don’t care to communicate with any nodes cast further afield in the network. But it made it very complicated and time-consuming for the more broad-minded, curious nodes to connect with a node on the other side of the network.
The culprit: a little something called minimum path length, which takes the average of path lengths between all possible pairs of nodes to determine, for instance, how long it might take for a signal to travel from a node on side of the network, to one on the other side. It’s an indication of the network’s efficiency. Here, you’ve got lots of local node connections with short path lengths, but the path lengths between pairs of distant nodes are very long.
Average all that out, and you get a minimum path length that is pretty long. Practically speaking, it becomes very inefficient and time-consuming to transmit a signal across a network, because it has to go through many, many short range connections before it can reach its goal. This is not the mark of a robust, efficient network. Any New Yorker who has taken the local 6 train from downtown to the Bronx during rush hour knows what I’m talking about, amirite? (It stops at Every. Frickin’. Station.) If you’re lucky enough to squeeze onto the express train, you can cut your commute in half.
So, okay: we’ve identified a problem. Watts and Strogatz decided to see what would happen if they did a bit of creative rewiring, replacing just a few of the short-range connections with long-range connections to nodes that were further afield. This didn’t affect the local clustering: you still had those little cliques. But it had a huge impact on the network’s overall efficiency, cutting the minimum path length significantly. Now a signal didn’t have to hop from one neighboring node to the next. It could take the express train instead of the local, thereby reaching its destination much more quickly.
That is the essence of a small world network: it defines that sweet spot between being too regular and too random, and the payoffs are immense. Plus, it’s not just for social networking in terms of applications — trivia games involving Kevin Bacon aside.

(This still ranks as one of my favorite commercials of all time.)
The US airline industry’s network of flights is the quintessential small world network. Sure, we all like to moan about the inconvenience of connecting flights, but thanks to that small world organization, we can usually get from any city to another within two flights — maybe three, for towns that are a bit more out of the way.

The United terminal at O'Hare

That’s because you have a lot of small local connections and a few major highly connected hubs providing those critical longer connections. In the end, your minimum path length is greatly reduced as a result. Imagine what a pain it would be if you had to hop from one local airport to the next to get from Los Angeles to New York.
Know what else makes good use of the small world model? Your brain. This is true both on a basic anatomical level (connections between neurons) and on a functional level, in terms of the synchronization with neurons in the cortex, which is where much of integrated processing takes place. Even large-scale neural networks like the visual system, or the brain stem, exhibit small world characteristics.
It makes sense when you think about it. In order to function efficiently, the brain must have local specialized “cliques” to process various kinds of sensory stimuli, for example, but it also needs to be able to distribute and integrate that information broadly throughout the brain.
"Yeah, I've only got 302 neurons, but it's a small world, baby!"

Somewhere along the evolutionary chain, Mother Nature hit upon small world organization as the best way to implement efficient information processing — hey, it works for the airline industry — and scientists have uncovered the evidence to that effect in several species, like C. elegans.
The nematode has a mere 302 neurons, one of the simplest neural systems, with something on the order of 2462 synaptic connections, and its architecture follows the small world model.
This does not appear to be a coincidence, according to several subsequent studies. One 2006 anatomical study found that neural connections in the cortex of both macaques and cats showed evidence of small world organization: high clustering and short path lengths.
And in 2010, scientists from the University of Notre Dame found similar organizational patterns in macaque brains; that structure was consistent across many samples. It was based on data resulting from 70 years’ worth of work by French researcher Henry Kennedy. His group injected ink tracers into the tissue, then put thin slices into a scanner to track the ink as it moved through the nerve cells.
The Notre Dame analysis revealed that the number of connections was largest between those areas of the brain that are closest to each other (local clustering, lots of short path lengths), declining as distance increases. But there are a few key long-distance connections, which seem to act like control switches, to coordinate how information is exchanged across the entire neural network. Sounds like a small world network to me.
The brain is a small world, too

For all its astonishing efficiency and robustness, when something goes seriously wrong in a small world network, the results can quickly become catastrophic. Sure, it can absorb the knocking out of a few local nodes here and there; but knock out one of those crucial hubs — well, we all know what happens to the airlines’ on-time flight schedules when a major SNAFU occurs at O’Hare.
Now imagine something like that happening in the brain. In many ways, the brain is surprisingly adaptive (“plastic”) and robust; it absorbs the loss of a few neurons here and there, and sometimes it can even rewire itself to compensate for more serious damage. But long-term damage over time, such as that wreaked by Alzheimer’s disease, leads to serious (and often heartbreaking) cognitive decline. And if you look at how those changes affect the brain’s functional networks, you’ll likely find — as reported in a 2006 study — that said cognitive decline is accompanied by disruption of the small world characteristics.
Airplanes, brains, and circles of friends — completely different, on the surface, yet all share a common underlying structure. If you want a network that is tight-knit, yet highly efficient, I’d suggest mimicking a small, small world.
Images: (top) Artistic visualization of six degrees of separation. Credit: Dannie Walker. Source: Wikimedia Commons. (center right) Chicago O’Hare International Airport. Credit: Robert Werner (2005, Vancouver BC), via Wikimedia Commons. (center left) C. elegans. Credit: Bob Goldstein, UNC Chapel Hill, via Wikimedia Commons. (bottom) Small world network in the brain. Credit: University of Notre Dame. Source: Science Daily.
He, Yong, Chen, Zhang J., and Evans, Alan C. (2007) “Small-World Anatomical Networks in the Human Brain Revealed by Cortical Thickness from MRI,” Cerebral Cortex 17 (10): 2407-2419.
Hilgetag, C.C. et al. (2000) “Anatomical connectivity defines the organization of clusters of cortical areas in the macaque and the cat,” Philosophical Transactions of the Royal Society of London B, Biological Sciences 355:91.
Markiv, N. T. et al. (2010) “Weight Consistency Specifies Regularities of Macaque Cortical Networks,” Cerebral Cortex 21 (6): 1254.
Masuda N., and Aihara, K. (2004) “Global and local synchrony of coupled neurons in small-world networks,” Biological Cybernetics 90:302-309.
Milgram, Stanley. “The Small World Problem,” Psychology Today, 1(1), May 1967, 60- 67.
Scannell, J.W., Blakemore, C., and Young, M.P. (1995) “Analysis of connectivity in the cat cerebral cortex,” Cerebral Cortex 15:1463-1483.
Scannell, J.W. et al. (1999) “The connectional organization of the cortico-thalamic system of the cat,” Cerebral Cortex 9:277-299.
Simard, D., Nadeau, L. and Kroger, H. (2005) “Fastest learning in small-world neural networks,” Phys Lett A 336:8-15.
Smith-Bassett, Danielle and Bullmore, Ed. (2006) “Small-World Brain Networks,” Neuroscientist 12(6): 512-523.
Watts, Duncan J., and Strogatz, Steven H. (June 1998) “Collective dynamics of ‘small-world’ networks,” Nature 393 (6684): 440–442.

Scroll to Top