'Small worlds' may provide big scientific opportunities


Monday, September 25th 2000, 12:00 am
By: News On 6


By Sue Goetinck Ambrose / The Dallas Morning News

Disney knew decades ago that it's a small world. Nowadays it's common folklore that any one person is connected to anyone else by just a few acquaintances.

But after all the singing, Disney never figured out what scientists now know: The world is full of small worlds never before imagined.

Two years ago, scientists came up with a mathematical formula of what would constitute a small world. With the formula, for example, they showed that Hollywood screen actors form their own small world. Stars who have never appeared in the same movie together, such as Anne Bancroft and Robert Redford, can be easily connected by shortcuts through other stars. (A popular game echoes this exercise: Players try to link a random movie star to actor Kevin Bacon in the shortest number of steps.)

Since then, other researchers have stepped into the world of small worlds. Neuroscientists have discovered that animal brains, and possibly people's, too, are small worlds, a finding that could lead to new ways to diagnose neurological diseases. Computer scientists are refining small-world math in hopes of streamlining highway, subway and even electronic traffic. Other researchers are studying small worlds to design electronic "agents" that can weave through the World Wide Web in search of specific information.

"If you understand why things work well, you have better ways to build things," said Dr. Massimo Marchiori of the University of Catania in Italy. "We already build highways that work more or less well, but you can try to improve."

Two key features make a world "small." Take a small-world network of acquaintances. First, certain people tend to be linked to each other in several ways, a feature called clustering. For instance, if Monique and Patty both know Hazel, Monique is more likely to know Patty than she is to know any other randomly chosen person on the planet, simply because Hazel might have introduced them. The three women are said to be clustered.

Second, the world is full of unexpected shortcuts. If Monique knows several people in a faraway place like Belgium, Hazel is automatically connected, with just two steps, to many people she's never met and probably never will.

"Shortcuts can help to make the world small, and you don't need many of them," said Dr. Steven Strogatz, an applied mathematician at Cornell University in Ithaca, N.Y., who along with colleague Duncan Watts came up with the first mathematical formulas to describe small worlds.

Of course, not all networks have shortcuts, so not all networks are small worlds, Dr. Strogatz said. For instance, the atoms in a crystal could be arranged in an orderly, cubic network resembling a three-dimensional checkerboard. If the lattice has a million atoms on each side, getting from one side to the other would take a million steps.

"There are no shortcuts," Dr. Strogatz said. "It's like a world with no highways."

But just as the U.S. interstate system made it easier to travel the country, mathematics shows it's easy to make the world small inside the crystal. A direct link between two far-apart atoms – only possible hypothetically in the crystal, of course – would constitute a shortcut.

"Almost as soon as you add the first couple of shortcuts, bam, you're almost at a small world," Dr. Strogatz said.

The mathematics behind small worlds could help scientists make faster or slower networks, Dr. Strogatz said.

"Things can spread fast in a small world," he said. "For an epidemic, that might be bad."

But, he said, "If you're an engineer trying to design ways of making the Internet faster, or cellular phones more efficient, or a transistor, you might ask how much would this benefit if I made these random [shortcut] connections?"

Scientists have already used mathematical equations describing the small-world phenomenon to judge the efficiency of transportation networks. For instance, Dr. Marchiori and colleague Vito Latora used a variation on Dr. Strogatz's equations to measure the efficiency of the subway system in Boston.

In a paper published recently on the World Wide Web (xxx.lanl.gov/abs/cond-mat/0008357), the Italian scientists found that Boston's subway system was indeed a small world.

"It's a very efficient way of transporting people around the area," Dr. Marchiori said.

Boston's subway system is only 58 percent less efficient than a dream subway that would connect every station directly to every other.

So if the dream subway (which of course would be far too costly to build) took passengers on average from one point to any other in a minute, Boston's subway takes only about 58 percent longer – about a minute and 35 seconds.

These kinds of efficiency calculations are important in designing networks, Dr. Marchiori said.

"We want networks that are very fast and efficient but are also economical," he said. "It's too expensive to connect everything to everything."

Since it would be useful – but not practical – to connect everything to everything, it might be useful to at least know how to get from one place to another. That's not obvious, if the place you want to get to isn't visible from where you are.

In other words, Hazel wouldn't necessarily know how to get to a particular person in Belgium. But, as Dr. Jon Kleinberg of Cornell University found in a recent study published in the journal Nature, if she knew Monique knew at least one person in Belgium, that would be a good place to start.

Dr. Kleinberg's calculations showed that surprisingly, it isn't efficient for people in the world to be randomly connected to many other people.

"It's not that you know too many people, but you can't decide which of the many will take you where you want to go," Dr. Strogatz said. "It's hard to zero in."

It's more efficient to have a few strategic connections that allow educated guesses to be made, Dr. Kleinberg found.

A lot of, but not random, connections also show up in the brains of monkeys and cats, said Dr. Olaf Sporns, a neuroscientist at Indiana University in Bloomington.

The brain, a collection of billions of interconnected nerve cells, is a network in the most literal sense. One nerve cell can reach out and touch thousands of others. Laboratory experiments have allowed scientists to map the connections between many clumps of cells in the cortex, the outer region of the brain responsible for high-level thinking.

Drawn on paper, the connections don't mean much.

"The drawing looks very confusing," Dr. Sporns said. "It looks like a bowl of spaghetti."

But when the connections are represented with mathematical formulas, out pops a small world, Dr. Sporns and his colleagues reported recently in the journal Cerebral Cortex.

"It allows us to see something we would have never seen otherwise," he said.

The average number of connections, or steps, between two areas of both animals' brains responsible for vision is less than two, Dr. Sporns said.

That suggests that every part of the brain can communicate with every other part via a relatively short path, he said.

Understanding links between different parts of the brain might help scientists see patterns that constrain how the mind thinks, he said. Mapping connections between brain areas in people could also help diagnose and describe the deficits that occur in neurological ailments.

Next, Dr. Sporns will test whether the connections between individual cells, rather than larger patches of cells, in the brain also form small-world networks. Scientists have already shown that the 302 total nerve cells of the worm Caenorhabditis elegans form a small world.

And Dr. Sporns said he has also discovered that small-world patterns may be an efficient way to fit so many nerve cells into the limited volume of the skull.

"So this may be another way in which having a small-world architecture is better," he said. "We use less volume for wiring and have more room for cells to process information."