Jon Kleinberg talks about algorithms, information flow, and
the connections between Web search and social networks.
A PrOFESSOr OF computer science at Cornell Uni- versity, Jon Kleinberg has been studying how people maintain social
connections—both on- and offline—
for 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
It started with Web search, and appreciating that in order to understand
Web search—which is about people
looking for information—we 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
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 blog-ging, writing product reviews, and
so on. And I’d see certain things be-
ing 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.
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
Where did your work go from there?
Once I had created the algorithm, I
realized there’s something very basic
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 paths—the proverbial
“six degrees of separation.”
The thing that intrigued me was
how creative [CONTINUEd ON P. 111]