GENE STANLEY is lecturing to an audience of physicists in Rome. Oddly enough, he is talking about yesterday’s trip to the airport. It had been late afternoon, and Stanley was in his office at Boston University for longer than expected, fighting with piles of papers. “I was sure I would miss my flight,” he says, “and miss a day in Rome, my favourite city in the world.”
But Stanley managed to beat the odds. Heeding the rush hour traffic, he deftly avoided several traffic jams by directing his taxi on a long and circuitous route. And this is precisely Stanley’s point: the shortest path is not always fastest. It might sound banal, but for his audience in Rome – researchers studying the emerging science of networks – this observation may have far-reaching implications.
In the past five years, researchers have discovered structural similarities between networks as diverse as ecological food webs, social organisations, the internet, and even the networks of molecular interactions that underlie cellular biochemistry. But network science is now attempting the next step: moving from theory to practical applications. And it’s throwing up some surprises.
Advertisement
In the real world, it turns out, the characteristics of these networks are not quite as they are in the laboratory models. But that’s not necessarily bad news; indeed, it is giving us a fresh insight into the nature of networks and providing new ways to cope with the complexities of modern life. Network researchers are now reckoning with how electricity, vehicles or information can flow easily through some links, and barely at all through others. It also means learning how to tell which links provide the most efficient route from one side of a network to the other. By pinning down these details, Stanley and other researchers hope to turn network ideas into network applications for a host of issues, from traffic management to internet searches.
But as up-to-the-minute as these applications may be, they are in fact based on an old and famous experiment. In 1967, Harvard social psychologist Stanley Milgram distributed letters to random individuals in Omaha, Nebraska, asking the recipients to forward the letters toward a stockbroker in Boston. The catch: they were only allowed to send the letter to someone they knew personally, and whom they thought would be socially “closer” to this stockbroker. Astonishingly, Milgram found that many of the letters made it to their destination in about six steps, leading to the now famous notion of “six degrees of separation” – the idea that we are all linked to one another through short chains of acquaintances.
It wasn’t until 1998 that mathematicians came up with the first explanations for Milgram’s result: the idea of “small worlds”. Duncan Watts and Steve Strogatz of Cornell University generalised Milgram’s experiment by considering a model network of points connected to near neighbours by a grid-like pattern of links. They also threw in a few random long-distance links between widely separated points (see “Small worlds”). Without the random links, the “diameter” of the grid-like network – the typical number of steps required to go from one element to another – would be comparable to the number of elements N. Written mathematically, D ˜ N. Obviously, if N is something like a million, this is no small world. But Watts and Strogatz found that the long-distance links make an enormous difference. They discovered that the diameter D of the full network, including these links, is comparable to the natural logarithm of N; that is, D ˜ ln(N). As mathematicians know, the logarithm is an extremely slow-growing function, so even for N equal to one million, ln(N) is of the order of 10. So adding just a few random links reduces the number of steps needed to “get around” in this network by a factor of 100,000 – much more like a small world.
Researchers have now demonstrated that many real-world networks are small worlds. In social networks, the internet and elsewhere, it takes only a few steps to go from any one point to another, even though these networks involve many thousands or millions of points. This picture seems true for virtually all networks.
But while this is clearly a welcome phenomenon – no matter how big the network, there’s always a quick way through it – there is something even more surprising beneath the surface. “Milgram’s experiment contains two striking discoveries,” says computer scientist Jon Kleinberg of Cornell University in New York State. The first is the well-known result that short chains abound. The second – and possibly more significant – discovery is that people are able to find them. The latter is particularly puzzling when you realise that we have only “local” knowledge of the social network. We know who our friends are, and also who some of our friends’ friends are, but not a lot more. “Milgram’s senders were essentially trying to perform a directed search in a very large social network about which they had very little information,” says Watts, now at Columbia University in New York City.
Each individual could only give the letter to someone he or she knew and thought might be closer, and then hope for the best. Yet this strategy somehow worked. Why? As researchers have now discovered, all networks may be searchable, but some are more searchable than others.
Kleinberg began investigating this issue in mathematical terms several years ago. First, of course, he had to define “searchable”. He decided that, given a network of N people, the network is searchable if there is some search strategy whose search time grows in proportion to some power of the natural logarithm of N. This definition is purely practical: if the search time took any longer, searching would simply take too long.
Then he returned to Watts and Strogatz’s model network of a grid-like set of elements with a few longer distance links thrown in at random. Of course, there are many ways to add such random links, adding mostly short or long links, for example, or some mixture of the two. But Kleinberg found that only one particular recipe led to an easily searchable network.
Where Watts and Strogatz created small worlds by adding a random scattering of links of random length, Kleinberg tried a wide variety of short cuts, varying the number of short cut links of any particular length. To create a searchable network, he found that longer links have to be less common than shorter links. In fact, the number of links of a particular length must decrease in proportion to the square of that length.
Adding extra links in this way provides a kind of optimal array of short cuts that complements the existing structure. As a result, short cuts of different lengths can be found near almost every point, making travelling through the network extraordinarily easy.
This result demonstrates that subtle features of a network can indeed determine whether local information is enough to direct signals across the whole structure. Since Milgram’s experiment clearly worked, it is clear that social networks have links that follow the subtle features of Kleinberg’s pattern. So what are they – what makes society searchable?
It’s a question that is well worth addressing because the answer may enable us to make all kinds of other networks searchable too. Watts thinks the answer lies in the way our society is organised into social groups. We live within communities, cities, regions and nations. At work, we belong to teams that are part of larger groups or divisions, which in turn sit within businesses in particular industries. Universities are organised similarly.
Last year Watts, along with Peter Dodds of the Earth Institute at Columbia and Mark Newman of the Santa Fe Institute in New Mexico, used Kleinberg’s insight to show that individuals can exploit these kinds of social groupings to navigate social networks efficiently. Their key insight is that social groups play dual roles. On the one hand, social groups serve to identify us with group labels. Jon Kleinberg, for example, is associated with the Computer Science Department of Cornell University. He shares these two associations with many others – fewer in the former group, more in the latter. On the other hand, social groups also serve as a starting point for forming social links. This is not surprising, as we tend to spend more time and have more in common with those in the same group.
It’s who you know
So you might suppose that because social groupings are associated with social links, a good strategy in a Milgram-type experiment would be to send the letters to the person you know who is most similar to the target in terms of group identity. Indeed, this is precisely what individuals in Milgram’s experiment did, sending their letters on to someone they felt was either geographically related to the stockbroker (living in the eastern US) or was in the same industry (finance or banking).
Watts’s team tested the effectiveness of this strategy in a series of computer simulations. Sure enough, they found that for realistic social groupings, individuals can indeed use this method to get messages to the target in a small number of steps. In effect, social groupings act as a set of visible labels that make it easy to see where actual social contacts might be likely. This feature is enough to make the network navigable in the way that Kleinberg defined.
In some ways it’s just common sense – faced with Milgram’s challenge, many of us would adopt these tactics without too much thought. Nonetheless, it is an important insight. Pinpointing exactly how people solved Milgram’s puzzle may have technological applications. As the world wide web continues to grow, even the most powerful search engines like Google are struggling to keep up. It is simply not possible for current search methods to scan quickly through the more than three billion pages on the web. As a consequence, Google maintains an evolving, centralised index of what’s out there and searches that instead. But as Kleinberg points out, “there are an increasing number of settings where this is not feasible”. Late-breaking news, for example, won’t show up in the index for some time.
Understanding searchable networks may help. In Milgram’s experiment, people used extra information – some similarity between a person and the ultimate target – to send letters effectively on their way, so why not try the same thing with web pages? Why not provide labels – similar to social groupings – that could send search engines towards target pages more quickly? The semantic web, where internet pages are tagged in such a way that search engines get a good idea of their content, is one approach that is already in development. At the Indiana University school of informatics, computer scientist Fil Menczer is working out other ways in which small worlds theory can make a more searchable web.
Despite all these advances in understanding, one newly discovered characteristic of networks in the real world threatens to render small worlds useless in many applications. At times, the small world itself can break down. That’s because, as Stanley’s trip to the airport illustrates, each link in a network may have some “cost” associated with it: Stanley, for instance, had to drive much further than he wanted to get to the airport. When these costs come into play, the shortest route from A to B may no longer be the cheapest or fastest (see “Destroying the small world”). Such inequality of links can be the undoing of the small world.
To explore this potential breakdown, Stanley and his colleagues, including Lidia Braunstein of the National University of Mar del Plata in Argentina, and Shlomo Havin of the Bar-Ilan University in Ramat-gan, Israel, built a mathematical network in which the links were assigned different costs at random. They then calculated the average length of the optimal, lowest-cost paths in the network.
They found that as long as the variation in the cost of the links is small, the lowest-cost paths between two points remain pretty much like the shortest paths. The average length of the optimal paths still depends only on the logarithm of N. Conclusion: for small variations in the links, a small world remains small.
But things change if the cost variation between links becomes larger – if the internet, for instance, were composed of high-speed and extremely low-speed connections. For large variations in the cost of links, the researchers found that the average length of the lowest-cost paths depends not on the logarithm of N but on N raised to some small power. For a Watts-Strogatz type network, for example, this power is 1/3 – the cube root of N. In this case, the average length of the lowest-cost paths increases tenfold. Only by meeting the extra cost will you be able to travel the shortest route. In other words, if the cost is more important to you than the path length, the network’s “small world” property is of no practical benefit. Whatever you want to do, you’re in for the long haul.
This breakdown of the small world could prove disastrous in some real-world settings, Stanley says. Varying the cost of a network’s links could change the searchability of a network, for example, so creating a searchable network may depend on achieving uniformity in its links. Or consider the broadcasting of video over the internet – an important commercial goal for the next decade. “If you want to watch a video on the web,” Stanley points out, “it is very important that the information arrives in a timely fashion.” But low-bandwidth internet links that handle such large data files slowly can have a disproportionate effect on performance. “The slowest link dictates the transmission time,” says Stanley. In effect, these weak links turn a small world into a slow world. And even if routing software tries to avoid these slow links, the optimal path is still a poor compromise. As a result, low-speed bottlenecks hamper the effectiveness of the entire network.
But a clear understanding of this problem suggests a solution. For instance, it may be possible to boost the performance of the entire internet by identifying the key bottlenecks and boosting their capacity.
Stanley also points out that the bottleneck idea could be enormously useful in the automated management of traffic flow. We naturally adjust our travel plans when traffic or some other disruption makes some roads far more attractive than others, and most in-car route-planning software already acknowledges that different routes have different costs, distinguishing between shortest routes and fastest-moving routes. But these “fastest routes” may not actually be so, as they are based on an average picture of traffic flow in the recent past.
Stanley suggests that “the car should know the traffic” by receiving up-to-the-minute information, allowing it to calculate a faster route that is much closer to the true optimum. Traffic is unavoidable, and optimal routes will never match the shortest routes of the ideal small world. But real-time traffic feedback would at least enable cars to avoid bottlenecks as they develop. “It would be relatively easy to do,” Stanley adds. “It just hasn’t been done yet.”
It seems an odd state of affairs in a new scientific discipline, but research into social networks has already come full circle – it could soon be helping scientists get to conferences on time, perhaps helping them work out where to take the subject in the future. Of course, we’ve always known that science proceeds by tortuous and convoluted paths, but in this area, at least, we shouldn’t be surprised.
- Mark Buchanan’s Small World: Uncovering nature’s hidden networks is published by Orion books