Six degrees of separation

Robert Matthews

Take a spot of fancy maths and watch how close you get to the superstars

WHAT has Hollywood actor Kevin Bacon got in common with worms and the US power grid? All have been linked by a mathematical explanation of the so-called small-world effect, in which apparently unrelated people turn out to have friends in common. This effect could also help our understanding of a wide range of problems, from the way disease spreads to brain seizures.
It turns out that the effect turns up in any type of network, from the film industry to the nervous system of living organisms. All that's needed is for a tiny proportion of the connections to link up with distant parts of the network.
Duncan Watts and Steven Strogatz at Cornell University in Ithaca, New York, made their discovery while they were studying networks whose connections could be altered at random. Until now, most research into networks has focused on two broad types. So-called regular networks have every point connected in the same way to the same number of neighbours: for example, just four connections to the four nearest neighbours. These networks are also highly clustered: nearby points are connected by a high density of links.
At the other extreme, a random network has points connected haphazardly -some to their nearest neighbours, but many more to distant parts of the network. As a result, the network has a relatively small "step-length", a measure of the typical number of steps between any two points. However, such graphs also have little clustering of nearby points. But what about networks that are in between - neither random nor regular? In computer simulations of these, Watts and Strogatz have shown that introducing just a few distant connections in a regular graph is enough to drastically cut the step-length - and yet still retain high levels of clustering.

Making Connections

In other words, such "semi-random" networks are very likely to show the smallworld effect, with apparently unrelated clusters joined to others via few steps. Watts and Strogatz found that having just 1 per cent of the connections linked to distant parts can trigger the effect.
To find out if this was more than just a curiosity, Watts and Strogatz calculated the step-lengths and clustering levels of three real-life networks: film actors, the electric grid of the western US and the nervous system of a nematode worm. In each case, the step-lengths were small-suggesting that they were random networks. But all three also had the high levels of clustering expected of regular networks, confirming that they exhibit the small-world effect.
According to Strogatz, film buffs have long recognised its presence in the movie world. "There's even a game people play where you have to connect any given actor to Kevin Bacon," says Strogatz. "It turns out he can be connected to virtually any other in no more than four steps." It's now clear that the Bacon game works because a small number of actors have played opposite some very unusual partners. "Bacon can be linked to Chaplin in just three steps, through films starring Laurence Fishburne and Marion Brando," says Strogatz.
As Watts and Strogatz report in Nature (vol 393, p 440), the small-world effect also has some serious implications. A small-world model of infections reveals that a few people can dramatically speed the spread of disease by crossing social or geographical boundaries. "You don't need to know any of these people yourself to be connected to a high-risk group," says Watts.
"This work is exceptionally significant," says William Ditto of the Georgia Institute of Technology, Atlanta. "It's amazing that one principle connects so many phenomena. We're already busy looking at its effects in electronic circuits and duration of seizures in the brain."

Email to test "six degrees of separation"
An unexpected e-mail from a US university over the coming months may not be spam - it could be from scientists investigating a fascinating social phenomenon. According to urban folklore, everyone in the world knows everyone else via just a few intermediaries - an effect summed up by the phrase "six degrees of separation". The number six emerged from an experiment performed in 1967 by the social psychologist Stanley Milgram, who sent packages to several hundred randomly selected people in America's Midwest, with the aim of getting them delivered to target people in Boston. Each recipient was given some details about the target, such as their name and profession, and was asked to send the package to a personal acquaintance whom they believed was more likely to know the target personally. Milgram discovered that on average the packages reached their targets after passing through astonishingly short chains, typically comprising just six people.

Small world
In 1998, mathematicians Duncan Watts and Steven Strogatz at Cornell University showed that Milgram's finding can be explained by the "small world effect", in which just a handful of people with very diverse friends can "short circuit" otherwise huge networks of acquaintances. But attempts to replicate Milgram's findings have had mixed results - and in any case, the original experiment fell far short of proving that the "six degrees" effect holds true for the whole world. So a team at Columbia University is now using the internet to attempt a global version. Instead of a postal package, they are inviting people to use their network of acquaintances to get an e-mail message to targets spread across the world. According to Watts, who devised the experiment, e-mail is ideal for testing Milgram's claim as there are well over 100 million e-mail users worldwide. Only e-mails between genuine acquaintances will be deemed to complete a chain. People will not be allowed to short-circuit the sequence by just looking up the target's e-mail address.

Chain mail
Watts has set up a website giving details about how to take part, and how to volunteer to act as a target. "Ideally, we'd like to have, say, 100,000 people, each trying to reach around 20 targets," he says. The team is keen to have as many people take part as possible, not least because they suspect people's mistrust of unsolicited e-mail might otherwise scupper their experiment. Early tests show that barely one in four e-mails are being passed on. With such a high rate of attrition, many thousands of people would have to take part to give much chance of even one chain of acquaintances reaching the target if Milgram's six degrees apply worldwide. "Perhaps people can't be bothered to pass them on - or perhaps Milgram was just wrong," says Watts. "Either way, we need lots of people to take part so we can tell." - Robert Matthews - [New Scientist 23 January 02]

DEMAGOGUES AND THE PRISONER'S DILEMMA. Charismatic leaders and media personalities can be destabilizing influences on social groups, according to various "small-world network" models. This conclusion that seems intuitively consistent with historical events such as civil uprisings and religious movements. But, surprisingly, long range connections in a network (which reduce the degree of separation among members) seem to hinder the system's return to equilibrium, according to a new model that combines small-world scenarios with a version of the "prisoner's-dilemma" proposition, according to which a pair of captured criminals ponder strategy: if neither criminal confesses, both go free; if one confesses, the other receives a stiff sentence; if both confess, they each receive moderate sentences. The study may help us to understand the dynamics of such social behaviors as smoking among teenagers, which is influenced by various factors including local social surroundings and the examples set by media role models. A collaboration of researchers from Ajou University, Chungbuk National University, and Seoul University in Korea, and Umea University in Sweden recently discovered the instability introduced to social systems by influential persons in a simplified, two-dimensional, small world network. The researchers (Beom Jun Kim,, 82-31-219-2571) created a 1024-element grid of points that represented an interconnected group of individuals. Some points in the grid were randomly designated to be cooperators (e.g. nonsmokers), and others were designated to be defectors (e.g. smokers). Once the grid was established, the individuals began playing a version of the prisoner's dilemma game with their eight nearest neighbors. The classic prisoner's dilemma is a game involving two players who each decide whether or not to cooperate with authorities in efforts to minimize their own prison sentences. In the new small-world/prisoner's-dilemma model, each individual surveys his nearest neighbors and scores points depending on their own status as a cooperator or a defector, and the statuses of their neighbors. The individuals may then change their status based on their score after each round of the game. To model the effect of an unusually powerful individual, the researchers made connections from a single influential member to several distant network members. In real life, for instance, the influential member might represent a celebrity or religious demagogue with access to the media or the Internet. When the influential member was a defector, the network collapsed into a numerical kind of anarchy, with many cooperators defecting as well. Eventually, the benefits of cooperating return the system to equilibrium, but the more long range connections in the network, the slower the system's recovery. Although the model is clearly a crude reflection of human interactions, it suggests that increasing numbers of long range connections between people may help destabilize communities. The result is in contrast to the general perception that connections across cultures and nations is exclusively beneficial to society. (B.J. Kim et al., Phys. Rev. E, August 2002)

SENSELESS SPAMMING You want to know the date of an upcoming concert. You're thinking of emailing everyone in your address book. Think again. If you really want to know something, don't send your question to hordes of people. That was psychologist Greg Barron's hunch. And now he's got the evidence...

Sixth sense
We have a subconscious ability to recognise people who are likely to cheat or double-cross us. Scientists at Hokkaido University in Sapporo, Japan, took pictures of people playing a game called the prisoner's dilemma, where you can either cooperate with an unknown partner to share a reward, or try to cheat the partner out of the whole reward. These pictures were later shown to students in another experiment. Without knowing who had done the dirty, the students were more likely to remember cheat's faces when they saw their pictures a second time, suggesting there is something detectable about a dishonest face (Evolution and Human Behaviour, vol 24, p 290)
[New Scientist 9 Aug 2003]

E-mail Study Corroborates Six Degrees of Separation

Image: COURTESY OF DUNCAN J. WATTSChances are, you don’t personally know any Australian policemen, Estonian archival inspectors or Norwegian army veterinarians. But you could probably get in touch with one of these distant individuals through a friend, or a friend of a friend, or a friend of your friend’s friend. The notion that every person on the planet is separated from everyone else by a chain of about six people has been around for some time. A report published today in the journal Science provides experimental data from the Internet in support of that claim.
The proverbial "six degrees of separation" was first proposed in 1967 by sociologist Stanley Milgram. Milgram asked 96 randomly selected people around the country to send a piece of mail to an acquaintance, who would send the mail along to another acquaintance, in an attempt to reach a designated "target" person in Boston. The messages that actually made it to their destination passed through an average of six people. But Milgram’s experiment was fairly small and has since been questioned by some sociologists. Peter Sheridan Dodds and his colleagues at Columbia University conducted a modern version of this study on the Internet, recruiting over 60,000 participants from 166 different countries for the experiment.
"If we tried to do this with paper, it would be completely unfeasible," says study co-author Duncan J. Watts. Study volunteers were given the identity of a target individual (one of 18 located around the world) and instructed to send an e-mail message to someone they thought could get the message closer to the target. The high number of participants turned out to be necessary for this global study, as only 384 e-mail chains (3 percent) actually found their way to the targets’ inboxes. The average completed chain comprised four people—an artificially low figure because the longer the chain, the less likely it was to reach its intended destination. By factoring in the rate of dropouts, the researchers calculated a median chain length of between five and seven people.
The study of social networks tends to attract the interest of researchers from many disciplines. Scientists hope it will shed light on such questions as how diseases spread, how people find jobs and how criminals can be caught. In addition to strengthening the six-degrees claim, the Columbia study concluded that successful message transmission did not rely as much on "hubs"—individuals with unusually high numbers of acquaintances—as was previously suspected.
"If you’re trying to send something to Siberia, you don’t think, ‘Who do I know with a lot of friends?’" Watts remarks. "You think, ‘Who do I know who is Russian?’" The authors further observe that perception of the chance of success can affect the actual success rate. Those participants given targets who seemed relatively easy to reach (but who were not, in reality, much more "connected" than other targets) were far less likely to drop out of the experiment. This in turn led to a far higher success rate in a kind of self-fulfilling prophecy--a point worth noting by those networking for a new job. Dodds and his colleagues plan to conduct further network studies on the Internet. Those interested in participating can sign up at --Dan Cho
[Scientific American August 08, 2003 ]

When things go wrong,it really is a small world

A node is missing!
The old saying "It's a small world" has taken on a grim new significance for 50 million people in America and Canada, now they have experienced that is being seen as the power failure in history.
While the precise cause of the breakdown is still being investigated, it's clear that the mathematics of networks lies at its core. Today's world is replete with networks, and they work well most of the time.
But when they break down, they can really ruin your day, as the mathematician Dr Duncan Watts of Columbia University makes clear in his new (and by some distance, the best) book on the phenomenon, Six degrees: The Science of a Connected Age (Heinemann, £20).
The book gets its name from that bit of urban folklore about how we live in a small world, in which we are all just six handshakes away from anyone else. In 1998 Watts, post-graduate at Cornell University, New York, and his supervisor Professor Steve Strogatz showed how this comes about. Simulating networks on a computer, they found that if just one per cent of the links in a network are random, the number of jumps needed to connect up any two parts of the network plummets by 90 per cent.
So, for example, just one British charity worker can put thousands of villagers across Africa within a handshake or two of each other- along with of his own friends back in Britain.
All very amusing, but there was also a darker side to the discovery. Watts and Strogatz gave some real-world examples of "small world" networks, including the power grid that supplies US cities west of the Rockies, it was this which keeled over in August 1996, when a single short-circuit triggered America's last catastrophic power failure.
Their 1998 paper thus contains a warning to pay heed to the nature of networks and the way that they are connected up. For, as Watts makes clear in his engrossing new book, it doesn't take much to turn a huge network into a small world - and an effective network into a world of pain.
It is not only obvious examples of networks such as power grids that are vulnerable, as Watts illustrates with events that befell the Japanese car manufacturer Toyota in 1997. Behind the corporate logo, this industrial giant is really a network of around 200 separate companies united by the need to feed the beast that is the Toyota Production System. Considered almost a religion among the companies, the TPS binds them all together, creating an astonishing level of shared expertise and resources, even among apparently competing suppliers.
For years the sprawling network of the TPS seemed to be far more effective than the vertical business architectures of US companies like Ford. Until, that is, the morning of Saturday, February 1, 1997, when the Aisin P-valve factory in Kariya, central Japan, burned down.
P-valves are a critical component of the brake systems of all Toyota vehicles, and Aisin was the sole supplier of them. Worse, the Kariya plant was Aisin's sole source of them. Worst of all, the tight-ship mentality of the TPS meant that Toyota held only two days' worth of stock.
By Wednesday, Toyota's entire production network -normally churning out an incredible 15,000 cars a day -had stopped. The P-valve factory had emerged as a critical "node" of the network, and its destruction had brought the company to its knees.
The story highlights the critical importance of identifying such nodes, and taking measures to minimise the impact of their failure. As Watts points out, however, the denouement of the story holds lessons that are even more important.
Within three days of the fire, more than 60 companies belonging to the TPS had become temporary P-valve makers, despite having no previous experience. Barely a week after the fire, Toyota was churning out almost as many cars again.
This astonishing recovery was made possible by the flipside of the network effect. Apart from the Aisin factory, the TPS network was still intact - it just wasn't producing anything. So the astonishing level of communication and mutual trust of the TPS was still there, allowing the other companies to put their heads together and plug the gap with minimal fuss.
According to Watts, Toyota's recovery hints at the possibilities of "self-healing networks" whose properties have yet to be fully understood by mathematicians. Perhaps President Bush should give a network of mathematicians a few million dollars to find out more, rather than throwing billions at a power grid that just can't help but fail again.
[Robert Matthews, The Sunday Telegraph 24Aug 2003]





Chaos Quantum Logic Cosmos Conscious Belief Elect. Art Chem. Maths

New Scientist 6 June 1998   File Info: Created 21/6/2002 Updated 9/7/2004 Page Address: