MacArthur Fellows Program

Jon Kleinberg

Computer Scientist | Class of 2005

Revealing the deep structure of complex networks such as genomes or computer networks, and creating new methods to extract the information embedded in them.

Computer Scientist
Cornell University
Ithaca, New York
33 at time of award

Jon Kleinberg is a computer scientist with a reputation for tackling important, practical problems and, in the process, deriving deep mathematical insights. His research spans diverse topics ranging from computer networking analysis and routing, to data mining, to comparative genomics and protein structure. He is best known for his contributions to two aspects of network theory: "small worlds" and searching the World Wide Web. Since the original demonstration by Milgram, it has become widely understood that any two people are linked by a relatively small number of connections among mutual acquaintances ("six degrees of separation"). Kleinberg extended this concept by introducing the notion of navigability – essentially, the information structure of the network necessary for individuals efficiently to make distant connections based solely on local information. Surprisingly, he was able to prove that, while certain architectures can be computationally efficient, no algorithm can find the shortest path in networks with short, random connections. This demonstration has important implications both in sociology and in distributed network architecture design (e.g., peer-to-peer file sharing). In addition, Kleinberg has developed an algorithm for identifying the structure of web site interactions; his algorithm distinguishes "authority" sites, which contain definitive information, from "hub" sites, which refer to authority sites using hyperlinks. Beyond immediate application in the development of web search engines, this algorithm makes it possible to identify communities of interest on the web without explicit effort needed by members (even without awareness of the existence of the community). 

Jon Kleinberg received an A.B. (1993) from Cornell University and an S.M. (1994) and a Ph.D. (1996) from the Massachusetts Institute of Technology. He has held research positions at IBM in the Theory and Computation Group (1995), the Computer Science Principles and Methodologies Group (1996-97), and, since 1998, continues to be a member of the Visiting Faculty Program at the IBM Almaden Research Center. He is a professor in the Department of Computer Science at Cornell University, where he has been on the faculty since 1996.

News About this Fellow
December 8, 2016
"A Guide to Solving Social Problems with Machine Learning"
Harvard Business Review
Sendhil Mullainathan , 2002 MacArthur Fellow
Jon Kleinberg , 2005 MacArthur Fellow
August 22, 2012
“Computational Social Science: Making the Links”
Jon Kleinberg , 2005 MacArthur Fellow
View all news


Photos are owned by the MacArthur Foundation and licensed under a Creative Commons license: CC-BY.
Credit: John D. & Catherine T. MacArthur Foundation.

Right-click on a link below to save the file to your computer.

More Fellows

View All 2005 Fellows

Stay Informed
Sign up for periodic news updates and event invitations. Connect with us on Twitter, Facebook, and YouTube.