Features

GPS, Q3: You have made major contributions to social network analysis and "small-world" networks. For readers that are not familiar with this field, can you summarize the key ideas in 2-3 paragraphs?

Kleinberg: While on-line information networks such as the Web are relatively recent in origin, social networks extend back to the earliest parts of our history. In a social network, nodes represent people or other social entities, and links indicate some kind of social interaction (for example, friendship, collaboration, or influence). Social networks have been central objects of study in the social sciences for a long time, since they have the potential to help illuminate how social outcomes can arise not just from the properties of individuals in isolation, but from the pattern of interactions among them -- in other words, from the structure of the network.

When you look at large-scale social networks drawn from different settings, you see a number of recurring patterns. A central one is the "small-world phenomenon" -- the fact that most pairs of people in a large social network are connected by very short paths. The social psychologist Stanley Milgram provided perhaps the first strong empirical evidence in support of this in the 1960s, using a now-famous experiment in which he asked people in the Midwest to forward letters through chains of friends to a "target" person in a suburb of Boston. Among the paths that successfully reached the target, the median length was six, a number that has since entered pop culture as the "six degrees of separation." There have been a number of mathematical models aimed at capturing the abundance of short paths in social networks; the 1998 work of Duncan Watts and Steve Strogatz in particular catalyzed a huge amount of research along these lines.

I became interested in the small-world problem because of what I viewed as the striking algorithmic content of Milgram's experiment: that the people taking part in the experiment were in fact performing a kind of decentralized routing. Each person had only local information about the network, but collectively they were able to route the message to a far-awar destination. My work on this problem centered around the development of social network models, building on the Watts-Strogatz framework, in which one could quantify the power of such decentralized algorithms.

More generally, there are huge opportunities at the moment in the study of social networks, since the digital traces of on-line communication have produced huge datasets on social interactions. There has also been the creation of new social structure on-line, through social networking sites such as Facebook and many other kinds of collaborative on-line media. A deep understanding of such data will require the collaboration of computing and information science with the social sciences -- a kind of synthesis that we're actively pursuing at Cornell.

What's this?