Six degrees of separation
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,
beomjun@ajou.ac.kr, 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... http://www.newscientist.com/exc/enews.jsp?id=ns99992557 |
| 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
Chances 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
http://smallworld.columbia.edu/.
--Dan Cho
[Scientific American August 08, 2003 ]
When things go wrong,it really is a small world |
 |
| 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] |