Jon Kleinberg

About Jon's Work

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). 

Biography

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.