Communications of the ACM
Last byte
Q&A: The Networker
Credit: Marc Smith
A professor of computer science at Cornell University, Jon Kleinberg has been studying how people maintain social connectionsboth on- and offlinefor more than a decade. Kleinberg has received numerous honors and awards, most recently the 2008 ACM-Infosys Foundation Award in Computing Sciences.
How did you first come to think about social networks?
It started with Web search, and appreciating that in order to understand Web searchwhich is about people looking for informationwe have to understand networks, and in particular networks that are created by people and reflect the social structure. You might look at the network within an organization to try to find the most central or important people. You can ask a similar question about the links among Web pages. And that becomes a way of finding the information that's been most endorsed by the community.
This was the motivation behind the hubs and authorities algorithm, which you developed in the mid-1990s and which uses the structure of the Internet to try to find the most authoritative Web pages.
In a sense, you can think about it as an attempt to automate something you could carry out manually. Suppose I were trying to buy a new laptop, for example. I'd find lots of people blogging, writing product reviews, and so on. And I'd see certain things being mentioned over and over, certain brands and laptops, and I might get some sense that here are the most popular ones. Those become the authorities, and the people who are best at mentioning them are the hubs. The best hubs reflect the consensus of the community, while the best authorities are that consensus, and the two reinforce each other.
Where did your work go from there?
Once I had created the algorithm, I realized there's something very basic about using these links and endorsements to evaluate things in a network. And that led to other areas, like citation analysis and, more broadly, the field of social networks.
Some of the most famous research in that field was done by Stanley Milgram, whose small world experiments in the 1960s established that we're all linked by short pathsthe proverbial "six degrees of separation."
The thing that intrigued me was how creative Milgram's experiments were. Essentially, what e'd done was create something that a computer scientist would recognize as a decentralized algorithm.
You're referring to an experiment in which Milgram asked a group of people in the Midwest to forward a letter to a friend of his near Boston.
Right. He gave them the man's name and mailing address and some basic personal details, but the rules were they had to mail it to someone they knew on a first-name basis. And no one had a bird's-eye view of the network, but collectively people were able to pass these messages to the target very effectively.
How does your own work fit into that picture?
What I did was use the 'algorithm' almost as a scientific probe of the structure of the network. I proposed a model for social networks that allows people to succeed at this kind of search, to land as close to the target as possible. There was a mathematical definition and linking trees and theorems. But the key feature is that we should create links at many different scales of resolution and in equal proportions.
Meaning?
There are levels of resolution we can use to think about the world. Geographically, there are people who are close neighbors, people who are nearby, people who are in the same region and country, and so on. It's important to have links across all these scales. If we only link locally, we can't get messages far away very quickly, but if we only create links at long ranges, then, for example, it would be very easy to get a message to the Boston area, but there would be no local structure to go the final few steps.
Have you been able to apply those findings to more technical topics?
One area where they prove to be useful is in the design of peer-to-peer networks. If you think about what a network is trying to do, it's trying to get information between pairs of computers that need to communicate, and it's trying to do this without any global knowledge of the network.
"A lot of the way we experience information online now is in a different form. It's coming to us continuously, in bite-size pieces, through our social networksblogs we read, things we see on Twitter, things our friends email us."
You've also been working on a different kind of Web search.
In the classical model of Web search, some centralized thing like a search engine gathers up lots of Web pages, and users come and issue queries and get answers. A lot of the way we experience information online now is in a different form. It's coming to us continuously, in bite-size pieces, through our social networksblogs we read, things we see on Twitter, things our friends email us.
How should our search tools and algorithms evolve to fit this new model?
One thing we should look at is a sort of temporal pattern, a pattern across time rather than across the network. So measures like chatter, bursts of activity, and upward and downward trends are going to be important, because they help us organize this kind of information. You see this increasingly on sites like Google News and Twitter search, which are essentially trying to give a time signature for certain stories.
©2009 ACM 0001-0782/09/1000 $10.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
No entries found