He received a Bachelor of Science degree in computer science from Cornell University in 1993 and a Doctor of Philosophy, from Massachusetts Institute of Technology in 1996.
He is the brother of fellow Cornell computer scientist Robert Kleinberg. Since 1996 Kleinberg has been a professor in the Department of Computer Science at Cornell, as well as a visiting scientist at International Business Machines Corporation"s Almaden Center. His work has been supported by an National Science Foundation Award, an Office of Naval Research Young Investigator Award, a MacArthur Foundation Fellowship, a Packard Foundation Fellowship, a Sloan Foundation Fellowship, and grants from Google, Yahoo!, and the National Science Foundation. In 2011, he was elected to the United States National Academy of Sciences.
In 2013 he became a fellow of the Association for Computing Machinery.
Kleinberg is best known for his work on networks and particularly for his HITS algorithm, developed while he was at International Business Machines Corporation. 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. Kleinberg has written numerous papers and articles as well as a textbook on computer algorithms, Algorithm Design, co-authored the first edition with Éva Tardos and sole authored the second edition His new book is entitled "Networks, Crowds, and Markets: Reasoning About a Highly Connected World", published by Cambridge University Press in 2010.
National Academy of Sciences.