Jon Michael Kleinberg (born 1971) is an American

computer scientist A computer scientist is a scientist who specializes in the academic study of computer science. Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...

and the Tisch University Professor of Computer Science and Information Science at

Cornell University Cornell University is a Private university, private Ivy League research university based in Ithaca, New York, United States. The university was co-founded by American philanthropist Ezra Cornell and historian and educator Andrew Dickson W ...

known for his work in algorithms and networks. He is a recipient of the

Nevanlinna Prize The IMU Abacus Medal, known before 2022 as the Rolf Nevanlinna Prize, is awarded once every four years at the International Congress of Mathematicians, hosted by the International Mathematical Union (IMU), for outstanding contributions in Mathematic ...

by the

International Mathematical Union The International Mathematical Union (IMU) is an international organization devoted to international cooperation in the field of mathematics across the world. It is a member of the International Science Council (ISC) and supports the International ...

Early life and education

Jon Kleinberg was born in 1971 in

Boston, Massachusetts Boston is the capital and most populous city in the Commonwealth (U.S. state), Commonwealth of Massachusetts in the United States. The city serves as the cultural and Financial centre, financial center of New England, a region of the Northeas ...

to a mathematics professor father and a computer consultant mother. He received a

Bachelor of Science A Bachelor of Science (BS, BSc, B.S., B.Sc., SB, or ScB; from the Latin ') is a bachelor's degree that is awarded for programs that generally last three to five years. The first university to admit a student to the degree of Bachelor of Scienc ...

degree in

computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

from

in 1993 and a

PhD A Doctor of Philosophy (PhD, DPhil; or ) is a terminal degree that usually denotes the highest level of academic achievement in a given discipline and is awarded following a course of graduate study and original research. The name of the deg ...

from

Massachusetts Institute of Technology The Massachusetts Institute of Technology (MIT) is a Private university, private research university in Cambridge, Massachusetts, United States. Established in 1861, MIT has played a significant role in the development of many areas of moder ...

in 1996. He is the older brother of fellow Cornell computer scientist Robert Kleinberg.

Career

Since 1996 Kleinberg has been a professor in the Department of Computer Science at Cornell, as well as a visiting scientist at

IBM International Business Machines Corporation (using the trademark IBM), nicknamed Big Blue, is an American Multinational corporation, multinational technology company headquartered in Armonk, New York, and present in over 175 countries. It is ...

's Almaden Research Center. His work has been supported by an NSF Career Award, an ONR Young Investigator Award, a MacArthur Foundation Fellowship, a Packard Foundation Fellowship, a Sloan Foundation Fellowship, and grants from Google, Yahoo!, and the

NSF NSF may stand for: Political organizations *National Socialist Front, a Swedish National Socialist party *NS-Frauenschaft, the women's wing of the former German Nazi party * National Students Federation, a leftist Pakistani students' political g ...

. He is a member of the

National Academy of Engineering The National Academy of Engineering (NAE) is an American Nonprofit organization, nonprofit, NGO, non-governmental organization. It is part of the National Academies of Sciences, Engineering, and Medicine (NASEM), along with the National Academ ...

and the

American Academy of Arts and Sciences The American Academy of Arts and Sciences (The Academy) is one of the oldest learned societies in the United States. It was founded in 1780 during the American Revolution by John Adams, John Hancock, James Bowdoin, Andrew Oliver, and other ...

. In 2011, he was elected to the

United States National Academy of Sciences The National Academy of Sciences (NAS) is a United States nonprofit, non-governmental organization. NAS is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Engineering (NAE) and the Nati ...

. In 2013 he became a

fellow A fellow is a title and form of address for distinguished, learned, or skilled individuals in academia, medicine, research, and industry. The exact meaning of the term differs in each field. In learned society, learned or professional society, p ...

of the

Association for Computing Machinery The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional membe ...

Research

Kleinberg is best known for his work on

networks Network, networking and networked may refer to: Science and technology * Network theory, the study of graphs as a representation of relations between discrete objects * Network science, an academic field that studies complex networks Mathematics ...

. One of his best-known contributions is the

HITS algorithm Hyperlink-Induced Topic Search (HITS; also known as hubs and authorities) is a link analysis algorithm that rates Web pages, developed by Jon Kleinberg. The idea behind Hubs and Authorities stemmed from a particular insight into the creation of w ...

, developed while he was at

. HITS is an algorithm for web search that builds on the

eigenvector In linear algebra, an eigenvector ( ) or characteristic vector is a vector that has its direction unchanged (or reversed) by a given linear transformation. More precisely, an eigenvector \mathbf v of a linear transformation T is scaled by ...

-based methods used in algorithms and served as the full-scale model for

PageRank PageRank (PR) is an algorithm used by Google Search to rank web pages in their search engine results. It is named after both the term "web page" and co-founder Larry Page. PageRank is a way of measuring the importance of website pages. Accordin ...

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 The small-world experiment comprised several experiments conducted by Stanley Milgram and other researchers examining the average path length for social networks of people in the United States. The research was groundbreaking in that it suggeste ...

. He was one of the first to realize that

Stanley Milgram Stanley Milgram (August 15, 1933 – December 20, 1984) was an American social psychologist known for his controversial Milgram experiment, experiments on obedience conducted in the 1960s during his professorship at Yale University, Yale.Blass, T ...

'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 the first edition with

Éva Tardos Éva Tardos (born 1 October 1957) is a Hungarian mathematician and the Jacob Gould Schurman Professor of Computer Science at Cornell University. Tardos's research interest is algorithms. Her work focuses on the design and analysis of efficient ...

and sole authored the second edition. Among other honors, he received a

MacArthur Foundation Fellowship The MacArthur Fellows Program, also known as the MacArthur Fellowship and colloquially called the "Genius Grant", is a prize awarded annually by the MacArthur Foundation, John D. and Catherine T. MacArthur Foundation to typically between 20 and ...

also known as the "genius grant" in 2005 and the

in 2006, an award that is given out once every four years along with the Fields Medal as the premier distinction in Computational Mathematics. His new book is entitled "Networks, Crowds, and Markets: Reasoning About a Highly Connected World", published by Cambridge University Press in 2010. Cornell's Association of Computer Science Undergraduates awarded him the "Faculty of the Year" award in 2002.

References

External links

Still the Rebel King -Video
Stephen Ibaraki *Yury Lifshits
Four Results of Jon Kleinberg: a talk for St. Petersburg Mathematical Society
{{DEFAULTSORT:Kleinberg, Jon American computer scientists 1971 births Living people 2013 fellows of the Association for Computing Machinery Members of the United States National Academy of Sciences MacArthur Fellows Nevanlinna Prize laureates Cornell University faculty Cornell University alumni Massachusetts Institute of Technology alumni 20th-century American engineers 21st-century American engineers 20th-century American scientists 21st-century American scientists Simons Investigator Recipients of the ACM Prize in Computing American network scientists