Jon Kleinberg

Infobox Scientist


image_width = 150px
name = Jon Kleinberg
box_width =
caption =
birth_date = October 1971
birth_place = Boston, Massachusetts
death_date =
death_place =
residence =
citizenship =
nationality = flagicon|USA American
ethnicity =
field = Computer Science
work_institutions = Cornell University
alma_mater = Cornell University
Massachusetts Institute of Technology
doctoral_advisor =
doctoral_students =
known_for =
author_abbrev_bot =
author_abbrev_zoo =
influences =
influenced =
prizes =
religion =
footnotes =

Jon Michael Kleinberg (born October 1971) is an American computer scientist and Professor of Computer Science at Cornell University.

Career

Jon Kleinberg was born in 1971 in Boston, Massachussetts. He received a B.S. in computer science from Cornell University in 1993 and a Ph.D., also in computer science, from MIT in 1996. Since 1996 he has been a professor in the Department of Computer Science at Cornell, as well as a visiting scientist at IBM's Almaden Research Center.

Research

Kleinberg is best known for his work on networks and particularly for his 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 such as PageRank by recognizing that web pages or sites should not only be considered important (as in PageRank) if they are linked to by many others, 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 with Éva Tardos. Among other honors, he received a MacArthur Foundation Fellowship in 2005 and the Nevanlinna Prize in 2006.

Trivia

Kleinberg is affectionately called the "Rebel King" by students (an anagram for "Kleinberg"). The Rebel King phenomenon began in an undergraduate course taught by Kleinberg, when an unknown student entered the lecture hall in the middle of class, announced in a loud voice that "Kleinberg is Rebel King," and then promptly left the hall. The Rebel King tradition continued in subsequent years with other classes taught by Kleinberg receiving similar visits. When Kleinberg co-taught a class with Eva Tardos, students also made an anagram of her name "Astro Dave", but it has not caught on. On March 28, 2008 Robert Kleinberg, Jon's younger brother, who is also a professor of computer science at Cornell, was interrupted during class by the entry of four students, at least one dressed as a bunny, who declared "Kleinberg is Rebel King? More like Rebel Prince!"

Jon Kleinberg's popularity among students is due in part to his excellence in teaching, which was formally recognized when Cornell's Association of Computer Science Undergraduates awarded him the "Faculty of the Year" award in 2002.cite web |url=http://www.cs.cornell.edu/Information/Awards/ByName/index.htm#_21 |title=Cornell CS Faculty Awards |publisher=Cornell University]

Notable Publications

* cite journal
author = J. M. Kleinberg
year = 1999
title = Authoritative sources in a hyperlinked environment
journal = Journal of the Association for Computing Machinery
volume = 46
pages = 604-632
doi = 10.1145/324133.324140
* cite journal
author = J. M. Kleinberg
year = 2000
title = Navigation in a small world
journal = Nature
volume = 406
pages = 845
doi = 10.1038/35022643
* cite book
last = Kleinberg
first = Jon
coauthors = Éva Tardos
title = Algorithm Design
publisher = Addison-Wesley, Boston
date = 2006
isbn = 0321295358

References

External links

* [http://www.cs.cornell.edu/home/kleinber/ Home page at Cornell]
* [http://www.macfound.org/programs/fel/fellows/kleinberg_jon.htm MacArthur Fellowship biography page]
* [http://www.youtube.com/watch?v=_bJ0dfp13Tg Still the Rebel King -Video]
*Yury Lifshits, [http://yury.name/talks/kleinberg-talk.pdf Four Results of Jon Kleinberg: a talk for St. Petersburg Mathematical Society]
*cite journal |last=Greuel |first=Gert-Martin |coauthors=Hopcroft, John E.; Wright, Margaret H. |title=The Mathematical Work of Jon Kleinberg |journal=Notices of the American Mathematical Society |volume=54 |issue=6 |year=2007 |month=June/July |pages=pp.740–743 |url=http://www.ams.org/notices/200706/tx070600740p.pdf |format=PDF |accessdate=2008-01-15