Funded Grants

Networks and contagion among people and computers

Six degrees of separation. Between us and everybody else on this planet. The president of the United States. A gondolier in Venice... It's not just the big names. It's anyone. A native in a rain forest. A Tierra del Fuegan. An Eskimo. I am bound to everyone on this planet by a trail of six people.

- John Guare, Six Degrees of Separation: A Play

The idea of the six degrees of separation?that you can get from anyone in the world to anyone else via a path of acquaintances only about six steps in length was introduced into popular culture with the words above, which come from John Guare's successful 1990 Broadway play, later made into a film. But the scientific result that underlies this idea, known as "the small-world effect," is much older. In the 1960s, the influential experimental psychologist Stanley Milgram performed an ingenious experiment in which he sent letters to 160 subjects chosen at random (roughly speaking) from the population of Omaha, Nebraska. The instructions accompanying the letters were simple. Each subject was to try to get their letter to the same target person, a stockbroker friend of Milgram's who worked in Boston, Massachusetts. But there was a catch: they were only allowed to send the letter to someone they knew on a first-name basis. Since it was unlikely that they would know a Boston stockbroker, the best they could do was to send the letter to someone whom they felt would be closer to the target person in some social sense-maybe someone who lived in Massachusetts, or some who worked in the financial industry. Then that person would repeat the exercise, until, by a succession of jumps, the letter would, with luck, find its way into the hands of its intended recipient.

Amazingly, 44 of Milgram's letters did reach the target. And the average number of steps they took to get there was just six. As the quotation above emphasizes, this result appears incredible to most of us. In a country with a population (at that time) of almost 200 million human beings, it took just six steps to get from one random person to another. Nonetheless, after many years and many other studies, we have found no reason to disbelieve Milgram's findings. It really is a small world.

Milgram's experiment was one of the first results in the field of social networks. If we were to draw a map of our society in which people were represented as points, and pairs of points were joined by lines when the people in question knew one another on a first-name basis, the resulting network would be precisely the social network over which Milgram's letters were transmitted. Many other complex systems also take the form of networks. Human and animal societies, the Internet, roads, the power grid, telephone calls, the World-Wide Web, who works with whom, who sleeps with whom, and even the body's metabolism or the English language, can all be thought of as networks. My work is about studying the shapes of these networks, especially social networks. If we can understand the way people are connected to one another, then it will help us to understand also how information spreads, how diseases are communicated, how communities form, and how society changes over time.

The work that my colleagues and I are doing has both experimental and theoretical components. We are interested in looking at actual networks in the real world and trying to determine their structure. Once we have gained some understanding of this structure, we use that information to construct mathematical and computer models of processes taking place on networks. Two examples demonstrate our approach.

Infectious diseases are spread by physical contact between individuals. The pattern of who has contact with whom forms a network, but in many cases it is not easy to determine what the structure of this network is--a cold can easily be passed between two people who stand in line together at the bank or sit in adjacent rows at the movie theater. There are some cases, however, where the network can be measured. In particular, networks are often quite clear in institutional settings--schools, hospitals, barracks, retirement homes, and so forth. In one current study, performed in collaboration with scientists at the Centers for Disease Control in Atlanta, Georgia, we looked at an outbreak of walking pneumonia in a hospital in Evansville, Indiana. The network in this case consists of patients confined to wards and caregivers who each work in one or more wards. Constructing mathematical and computer models of this network, we simulated the progress of the outbreak through the hospital. Because of their movement between wards, we found that the caregivers were crucial to the spread of the disease, even though rather few of them contracted it. Based on these findings, we have been able to make new recommendations for controlling or preventing similar outbreaks in the fixture.

Another study looks at the networks by which computer viruses spread. Although human and computer infections appear in many ways to be quite different, it turns out that they can be studied using similar mathematical tools. Computer viruses mostly spread via email: a virus arrives on a computer in an email message, and then finds further computers to infect by scrutinizing the recipient's email address book - computer file in which a user stores the email addresses of his or her frequent correspondents. These address books form a social network of connections between people, whose structure we can probe by looking at the address book files. Starting with such address book data, we have reconstructed a picture of this network and, as with the pneumonia study, have been able to create a mathematical model of the spread of computer viruses which allows us to make specific new recommendations for controlling and preventing virus infection.

These are just two examples of the way in which the study of networks can help us understand how the world works and how specific problems can be solved. Other planned projects include studies of networks of collaboration between scientists and business-people, the structure of information networks such as the World-Wide Web and citation networks, and possibly networks of interaction between computer users in, for example, online auctions. Each of these has the potential to shed light on the forms of organization that societies choose and the way that organization affects the spread of information, be it scientific, professional, or personal. Theoretical analyses will include studies of the structure of sub-communities within larger networks, investigation of possible vaccination or other preventive strategies for contagion on human or computer networks, and studies of the structure of networks that grow and change over time, such as the Web.

Under the program to be funded by this grant, we will pursue these and other projects to gain an understanding of how networks of connection between people and computers drive the actions of that most fascinating of complex systems, human society.