Short Cuts

[John Dicus]

Do you think you see this happening during OS?

====

Mathematicians Prove That It's a Small World

By SANDRA BLAKESLEE (NY Times)
NEW YORK -- Mathematicians have found a simple explanation for how big
worlds can be turned into small worlds, a phenomenon summed up in the
popular belief that anyone on earth can be linked to anyone else by a chain
of only six other people -- the so-called six degrees of separation.

Any large set of linked, dynamic components -- be they people, electric
power stations, brain cells or whatever -- can be transformed into a small
world, the mathematicians said,  by introducing short cuts between a few
components. Relatively few short cuts can make big changes in a network,
linking clusters of people, power stations or brain cells together in
unexpected ways.

Among people, the short cuts are well-connected individuals -- those who
know many people from other countries, different disciplines or unusual
subcultures. Such highly  connected people establish surprising
interconnections between groups that seem  impossibly distant from one
another, like Iowa farmers and Kalahari bushmen. For example, sometimes a
farmer's son will join the Peace Corps in Africa and thus unexpected links
are born.

This kind of interconnectedness is familiar to social animals like humans
but now, for the first time, mathematicians have quantified it in a general
model.

The finding, which is the first mathematical explanation of the small world
phenomenon in dynamical systems, was reported in the June 4 issue of the
journal Nature. The  mathematical experiments were done by Steven Strogatz,
a mathematician at Cornell  University, and Duncan Watts, a postdoctoral
fellow in the social sciences at Columbia University.

"They have made a great contribution to understanding small world effects,"
said James  Collins, a mathematician at the Center for Biodynamics at Boston
University. "The phenomenon has been mostly studied by sociologists and
psychologists, but the mathematics community had not explored these networks
in terms of self-organizing systems."

Such systems include social networks, technologies like the Internet and
electric power grids, and life in general -- the fact that a sperm can
penetrate an egg and set into play a series of biological processes that
give rise to complex creatures from mere specks of protoplasm.

The finding that short cuts make all the difference explains why total
strangers can quickly determine that they have acquaintances in common, why
epidemics spread so rapidly in the modern world and may be useful in
improving communication systems like cellular  telephones and the Internet.

"There's a unifying mechanism in nature that makes things small and
interconnected," Strogatz said.

But could it be modeled mathematically? To find out, the researchers focused
attention on two extreme types of networks. One is a simple geometric
lattice in the shape of a ring, with each node connected locally to its
neighbors. Like a pure crystal, this lattice is highly ordered.The distance
from one node to the next is characteristically long, and nodes tend to
cluster tightly in neighborhoods.

The second model is a ringed lattice with the nodes connected randomly. The
distance from one node to the next is characteristically shorter, but
because everything is connected helter-skelter, there is very little order
and nodes do not fall into common clusters.

Most biological, technological and social networks lie between these two
extremes of ordered versus random connections. "We asked, what  would happen
if you take an ordered lattice and rewire some of the nodes, introducing
short cuts?" Watts said. "You'd be making a regular  network slightly more
random by connecting nodes that would not normally be connected."

For example, in a regular network each node is connected only to its
immediate neighbors -- like people in a rural village who rarely leave home
and only know the people next door. But if one of those villagers travels to
the big city, adding one distant link to all the close links at home, the
village is connected to the wider world.

The results were astonishing, Watts said. The properties of the lattice
change dramatically. It still forms clusters, but the pathways between
clusters are much shorter. Immediate neighborhoods and more distant
neighborhoods are suddenly closer together. Information spreads more
quickly. Each node has access to more information and can do more things. In
being connected to more neighbors, nodes begin to cooperate
and synchronize.

The huge surprise is that it takes very few short cuts between nodes and
clusters to turn a big world into a small world, Watts said. After a point,
adding more short cuts does not improve network efficiency.

To find out if their abstract mathematical model applied to the real world,
the researchers looked at three systems whose elements have been mapped
completely -- the power transmission grid of the western United States, the
282 neurons that make up the nervous system of a simple worm called
Caenorhabditis elegans, and the nearly 250,000 actors listed in the Internet
Movie Database.

 Each is a small world whose elements are closely connected to neighboring
elements -- one power station to the next, one cell to another and  one
actor to another actor who tends to be cast in the same kind of films, Watts
said.

Such worlds could be random but they are not. They have a great deal of
structure, which is created by short cuts between a few power  stations, a
few special cells in the nervous system or certain prominent actors who make
a lot of movies, Watts said. These short cuts can be identified and
measured, which means that they act as a unifying principle for small worlds
in general.

The finding of what difference a few short cuts can make has radical
implications for people, Watts said. Most people know only their immediate
neighbors and friends but a few people are well-connected.  They cross
geographic, social and political boundaries and make the world seem smaller.

For example, if you knew Secretary of State Madeline Albright, you would be
connected to everyone she knows, including kings and queens.  But even if
you are not her friend, you may be connected to her indirectly. Perhaps your
neighbor's daughter-in-law was Ms. Albright's college roommate. If so, you
would be connected to the Queen of England by three degrees of separation.

The notion that all people are connected through indirect networks was first
studied by the Stanley Milgram, a social psychologist at Harvard University
who in 1967 asked people in Nebraska and Kansas to mail a letter to two
people in Boston with whom they were not acquainted.  They were to forward
the letter to friends who might know the Boston people.

The average number of intermediaries between the Midwesterners and the
Bostonians was six, a finding that was popularized in the 1990 in the play
"Six Degrees of Separation," by John Guare. The play and a subsequent movie
were based on the notion that everyone in the world is connected to everyone
else through a chain of at most six acquaintances. If two people have one
mutual acquaintance they have one degree of separation. Subsequent degrees
of separation are based on the number of people needed to make the link.

A few years ago, college students embraced a game called "Six Degrees of
Kevin Bacon," in which they linked the actor to other actors through as few
links as possible. The Oracle of Bacon at Virginia, a Web site created by
Brett Tjaden, now links 322,095 actors to Bacon, assigning each a Bacon
score. Because Bacon has appeared in so many films, most actors have low
Bacon scores.

The game can also be played with a relative newcomer like Leonardo DiCaprio.
For example, DiCaprio was in "Les Cent et Une Nuits" (1995) with Harrison
Ford, who was in "Apocalypse Now" (1979) with Marlon Brando, who was in
"Countess from Hong Kong" (1967) with Charlie Chaplin. Thus, Chaplin has a
DiCaprio score of three.

Short cuts can have positive or negative effects on society, Watts said.
When human populations were isolated centuries ago, disease epidemics would
be localized. But add jet travel -- a short cut -- and the world becomes
smaller. Many experts believe that AIDS was first spread to the United
States from Africa through an infected airline attendant who introduced the
virus into gay bathhouses in New York.

"Infectious diseases spread more quickly and easily in a small world, and it
is alarming how few short cuts are needed to make the world small," Strogatz
said.

On the other hand, short cuts can make networks more efficient. One might
improve the efficiency of cell phone networks by deliberately introducing a
few random connections between nodes, or phones, Collins said. That alone
might improve traffic flow without building new relay stations. Similarly,
one might improve the flow of information through the Internet by
introducing a few random links between backbone computers on the Internet,
he said. That might reduce the time needed to send e-mail or to find a Web site.