Mark Buchanan

NEXUS

Small Worlds and the Groundbreaking Science of Networks

W.W.Norton 2002


KEYWORDS: SMALL WORLDS - SYNCHRONY - general organising tendency in nature - geometrical character of the social world - the strength of weak ties - mathematical networks - order and randomness in one network - small world networks -synchronisation puzzle - global organisation - computation - signals, counter-signals and counter-countersignals - computational design, small world architecture - small world geometry

pg 48

SMALL WORLDS - SYNCHRONY

....in the tropical rainforest of Papua, New Guinea... fireflies, first in pairs, then in groups of three, ten, a hundred, and a thousand will begin to pulse near-perfect synchrony....Chrickets to not send outbursts of light but of sound -chirps produced by rubbing their legs together - and on a hot summer evening a field full of crickets will synchronise their chirping..... the cardiac pacemaker is a bundle of our cells, each of which sends out an electrical signal to the rest of the heart, triggering its contraction. Like the crickets and fireflies, these cells manage to fire strictly in unison, with each collective burst triggering a single heartbeat. How does it work? How can a bunch of cells or crickets or anything else managed to synchronise their activity without the aid of any external guidance all orchestration?

This is a question not just of biology but of mathematics, for it seems to reach beyond the details of crickets, heart cells, or what have you, and to point towards some general organising tendency in nature. Indeed, in the past two decades, neuro-scientists have discovered that the synchronised firing of millions of neurons in the human brain appears to be essential to some of the most basic functions of perception. Something quite similar even takes place among the several hundred members of an enthusiastic audience, whose clapping sometimes falls into rhythmic perfection.

Small worlds

...the small-world problem

....you are " only six handshakes away from the President of United States" - Stanley Milgram (six degrees of separation)

....these publications certainly testify to the reality of the small world effect but offered little in the way of explanation. A few imaginative researchers had turned to a non-Euclidian geometry, the mathematical framework of Albert Einstein's theory of relativity, in the hope that it might offer some insight into the geometrical character of the social world. Non-Euclidian geometry makes it possible to talk about worlds in which space can be curved and distances work in utterly peculiar ways.

...Mark Granovetter's ideas about the strength of weak ties. Granovetter had argued convincingly that weak social bonds are the most crucial in tying together a society. Somehow, these links ultimately make for a small world.

What was lacking was a recipe for building precise mathematical networks that would bring the architecture of such a world into sharp relief.

Ordered networks give rise to clusters and cliques, just as we find in real social networks. But ordered networks to not have the small world property - it takes to many steps to get from one point to another.

In contrast, random networks make for small worlds but worlds without clusters, worlds in which there is no such thing as a group of friends or a community.

The proper recipe for a social network would have to involve a peculiar mingling of order and randomness in one network. From the mathematical point of view, the central question was how to do that...

To explore networks in the netherworld between chaos in order, Watts and Strogatz decided to start with a fully ordered circular network, each dot being connected to just a few of its closest neighbours. Then they could do some haphazard rewiring. Choosing a pair of dots at random, they could add a new link between them. Then they could choose another pair and do the same thing, and so on.

... the result was a networks still almost totally dominated by order, but with roughly 1 percent of its links now placed at random. Not surprisingly, this dusting of disorder hardly all to the clustering of the network at all.

Watts and Strogatz noticed, however, that while the scattered randomly links were having no effect on the networks clustering, they nevertheless were having had devastating influence on the number of degrees of separation. With no random links at all, this number had been roughly 50; now, but a few random links thrown in, it had suddenly plummeted to about 7. The lightest dusting of random links was enough to produce a small world.

So let's go back to a circle of 6 billion, the world's population, with each person linked to his or her nearest 50 neighbours. In the ordered networks the number of degrees of separation is something like 60 million - this being the number of steps it takes, even moving 50 at the time, to go halfway around the circle. Throw in a few random links, however, and this number comes crashing down. Even if a fraction of the new random links is only about 2 out of 10'000, the number of degrees of separation drops from 60 million about 8; if a fraction is three out of 10'000, it falls to five. The random links, being so few in number, have no noticeable effect on the degree of local clustering that makes social networks what they are.

These small world networks work magic. From a conceptual point of view, they reveal how it is possible to wire up the social world so as to get only six degrees of separation, while still permitting the richly clustered and interwined social structure of groups and communities that we see in the real world.

Even a tiny fraction of weak links - long-distance bridges within the social world - has an immense influence on the number of degrees of separation. We find here an explanation not only for why the world is small, but also why we are continually surprised by it. The long-distance social shortcuts that make the world small are mostly invisible in our ordinary social lives. We can only see as far as those to whom we are directly linked - by strong or weak ties alike.

pg 57
The synchronisation puzzle

In their earlier stab at the synchronisation puzzle, Mirollo and Strogatz had assumed that each firefly would "see" and respond to every other one. In a small of 10'000 fireflies, this would make for a total of about 50 million communication links between fireflies (one link for each conceivable pair). With such a dense web of connections, the group would have little trouble achieving and maintaining global organisation. Armed with the small world idea, Watts and Strogatz decided to revisit the issue. Could a swarm of fireflies achieve the same result with fewer communication links?

It would seem a bit more realistic to suppose that each firefly responds mostly to the flashing of a few of its nearest neighbours, although a rare few might also feel the influence of offline or a tool at the longer distance..... the flies would interact with one another in something like the small world patter. With this architecture, the same 10'000 flies would be trying to make do with many thousands of times fewer communication links than before. Now each would affect only a handful, perhaps as few as 4 or 5. This change in wiring diagram amounts to hacking out more than 99.9 percent of the links between flies. You would hardly expect any communication network to survive such as savaging, and yet this one did.

In a series of computer simulations, Watts and Strogatz found that the insects were able to manage the synchronisation almost as readily as if everyone were talking to everyone else. By itself, the small world architecture of the reduction in the required number of links by a factor of thousands. There is a profound message lurking here - the message not about biology but about computation.

From an abstract point of view, the group of fireflies trying to synchronise themselves is making an effort in computation. As a whole, the group attempts to process and manage myriads signals, counter-signals and counter-countersignals travelling between individual fireflies, all in an effort to maintain the global order. This computational task is every bit as real as those taking place in a desktop computer or in the neural network of the human brain. Whatever the setting, computation requires information to be moved between different places. And since the number of degrees of separation reflects the typical time needed to shuttle information from place to place, the small world architecture makes for computational power and speed.

Of course, no one knows how fireflies are really connect within a swarm. Indeed, only a few species manage the synchronisation trick.Watts and Strogatz had not answered all the questions about fireflies, and many remain unanswered still.

Nevertheless, they had learned that in terms of computational design, small world architecture is especially important "good trick". When it comes to computation, though, nothing is so wondrous as the human brain. And so it was natural to wonder, might the brain also exploit the small world trick?....Does it point to some deeper design principle of nature? In their three-page paper in the June 4,1998, issue of "Nature", Duncan Watts and Steve Strogatz unleashed all these findings on an unsuspecting scientific community. Their paper touched off a storm of further work across many fields of science. As we will see an upcoming chapters, a version of their small world geometry appears to lie behind the structure of crucial proteins in our bodies, the food webs of our ecosystem, and even the grammar and structure of language we use. It is the architectural secret of the Internet and despite its apparent simplicity it is in always a new geometrical and architectural idea of immense importance.










HOME      BOE     SAL     TEXTE