Kleinberg is best known for his work on
networks. One of his best-known contributions is the
HITS algorithm, developed while he was at
IBM. HITS is an algorithm for web search that builds on the
eigenvector-based methods used in algorithms and served as the full-scale model for
PageRank by recognizing that web pages or sites should be considered important not only if they are linked to by many others (as in PageRank), but also if they
link to many others. Search engines themselves are examples of sites that are important because they link to many others. Kleinberg realized that this generalization implies two different classes of important web pages, which he called "hubs" and "authorities". The HITS algorithm is an algorithm for automatically identifying the leading hubs and authorities in a network of hyperlinked pages. Kleinberg is also known for his work on algorithmic aspects of the
small world experiment. He was one of the first to realize that
Stanley Milgram's famous "six degrees" letter-passing experiment implied not only that there are short paths between individuals in social networks but also that people seem to be good at finding those paths, an apparently simple observation that turns out to have profound implications for the structure of the networks in question. The formal model in which Kleinberg studied this question is a two dimensional grid, where each node has both short-range connections (edges) to neighbours in the grid and long-range connections to nodes further apart. For each node v, a long-range edge between v and another node w is added with a probability that decays as the second power of the distance between v and w. This is generalized to a d-dimensional grid, where the probability decays as the d-th power of the distance. Kleinberg has written numerous papers and articles as well as a textbook on computer algorithms,
Algorithm Design, co-authored with
Éva Tardos. In 2010 he published his book "Networks, Crowds, and Markets: Reasoning About a Highly Connected World" at
Cambridge University Press. Cornell's Association of Computer Science Undergraduates awarded him the "Faculty of the Year" award in 2002. ==References==