From SIAM News, Volume 37, Number 3, April 2004

Social Networks Exposed

By Lada A. Adamic

Until the past decade, data about social networks was largely hidden and could be obtained only through patient field work. If you were a salesman trying to make a sale, or if you were looking for a job, you asked a friend, who asked an associate, and so on, tracking fine threads through the web of social contacts. If you were a clever sociologist by the name of Stanley Milgram, you recruited volunteers from Nebraska to pass messages through their friends to a target individual in Boston. If you needed a more complete, self-contained social network, you could try finding a captive and somewhat eager audience, such as a class of schoolchildren, and ask them to list their friends. These traditional approaches had some drawbacks: In addition to being very time consuming, they yielded only small datasets, typically consisting of only a few dozen individuals.

Things are changing, and quite rapidly. Not only is a lot of social interaction today captured through e-mail and instant messaging, but people are flocking to social networking sites, where they volunteer information about themselves and their social networks. These new services promise to help individuals utilize their social networks to find the social and business contacts they seek.

In our research at HP Labs, we took advantage of the availability of e-mail and online community data to study a classic problem: How and under what conditions are individuals able to search social networks? We simulated Milgram's experiment on a social network of about 400 individuals communicating via e-mail within HP Labs. Two individuals were considered connected only if they had exchanged several e-mails back and forth, so that the tie would potentially be strong enough to support a request to pass on a message. We then simulated a simple search: A randomly chosen individual needs to find a target, with the restriction that at each step the message can be passed only to one e-mail correspondent, someone who is "closer" to the target.

What we found is that the key to a successful search is a specific type of social structure. As shown in the accompanying figure, although most communication at HP Labs stays within organizational groups, there is also quite a bit of correspondence across the organization. This means that people can take shortcuts across the organization to get close to the person they need to contact; at the same time, once they get close there are enough short-range contacts to ensure that the target can be reached. Sometimes, as is the case in HP Labs, social distance also tends to correspond to physical distance, making it possible to search by office location. By comparison, an online community at a university did not lend itself to search as easily, which makes sense given the informal and loose nature of that network.

E-mail communication (gray lines) mapped onto the organizational hierarchy (black lines) at HP Labs, showing the tendency of communication to "cling" to the formal organizational chart.

These experiments are a validation of recently proposed models of social structure that enable search. For HP Labs, they also provide a way to understand how effectively structured the organization is, showing that individuals are able to use cross-organizational ties to quickly get the resources they need, rather than having to go all the way up and down the management chain. In general, e-mail communication can give insight into informal communities that may be forming outside the formal organizational structure to address new problems. It can also identify the central individuals and the gossips.

Beyond revealing the structure of social networks, e-mail and other online data present an opportunity to study the dynamics of information. How news propagates through a social network, and how the network itself evolves over time, are still open questions, requiring new network models and approaches.

Lada A. Adamic is a researcher in the Information Dynamics Lab at HP Labs.