Jump to content

Jon Kleinberg

From Wikipedia, the free encyclopedia
Jon Kleinberg
Kleinberg speaking at the Cornell/Microsoft Research International Symposium on Self-Organizing Online Communities
Born
Jon Michael Kleinberg

1971 (age 52–53)
Boston, Massachusetts
NationalityAmerican
EducationCornell University
Massachusetts Institute of Technology
Known forHITS algorithm
Awards
Scientific career
FieldsComputer Science
Institutions
ThesisApproximation algorithms for disjoint paths problems(1996)
Doctoral advisorMichel Goemans[2]
Websitevideolectures.net/jon_kleinberg
www.cs.cornell.edu/home/kleinber

Jon Michael Kleinberg(born 1971) is an Americancomputer scientistand the Tisch University Professor of Computer Science andInformation ScienceatCornell Universityknown for his work in algorithms and networks.[3][4][5][6][7][8][9]He is a recipient of theNevanlinna Prizeby theInternational Mathematical Union.

Early life and education

[edit]

Jon Kleinberg was born in 1971 inBoston, Massachusettsto a mathematics professor father and a computer consultant mother.[10]He received aBachelor of Sciencedegree incomputer sciencefromCornell Universityin 1993 and aPhDfromMassachusetts Institute of Technologyin 1996. He is the older brother of fellow Cornell computer scientistRobert Kleinberg.

Career

[edit]

Since 1996 Kleinberg has been a professor in the Department of Computer Science at Cornell, as well as a visiting scientist atIBM'sAlmaden 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 theNSF.He is a member of theNational Academy of Engineeringand theAmerican Academy of Arts and Sciences.In 2011, he was elected to theUnited States National Academy of Sciences.[11][12]In 2013 he became afellowof theAssociation for Computing Machinery.[13]

Research

[edit]

Kleinberg is best known for his work onnetworks.One of his best-known contributions is theHITS algorithm,developed while he was atIBM.HITS is an algorithm for web search that builds on theeigenvector-based methods used in algorithms and served as the full-scale model forPageRankby 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 theylink tomany 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 thesmall world experiment.[14]He was one of the first to realize thatStanley 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. 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 Tardosand sole authored the second edition.[5][15]Among other honors, he received aMacArthur Foundation Fellowshipalso known as the "genius grant" in 2005 and theNevanlinna Prizein 2006, an award that is given out once every four years along with the Fields Medal as the premier distinction in Computational Mathematics.[16] His new book is entitled "Networks, Crowds, and Markets: Reasoning About a Highly Connected World", published by Cambridge University Press in 2010.[17]

Cornell's Association of Computer Science Undergraduates awarded him the "Faculty of the Year" award in 2002.[18]

References

[edit]
  1. ^"ACM Awards".Archived fromthe originalon 2012-05-04.Retrieved2013-05-08.
  2. ^Jon Kleinbergat theMathematics Genealogy Project
  3. ^Kleinberg, J. M. (1999). "Authoritative sources in a hyperlinked environment".Journal of the ACM.46(5): 604.CiteSeerX10.1.1.54.8485.doi:10.1145/324133.324140.S2CID221584113.
  4. ^Kleinberg, J. M. (2000)."Navigation in a small world".Nature.406(6798): 845.Bibcode:2000Natur.406..845K.doi:10.1038/35022643.PMID10972276.S2CID4425543.
  5. ^abKleinberg, Jon;Tardos, Éva(2006).Algorithm Design.Addison–Wesley, Boston.ISBN978-0-321-29535-4.
  6. ^Jon M. KleinbergatDBLPBibliography ServerEdit this at Wikidata
  7. ^Jon Kleinberg's publicationsindexed by theScopusbibliographic database.(subscription required)
  8. ^Jon Kleinbergauthor profile page at theACMDigital Library
  9. ^Kempe, D.; Kleinberg, J.; Tardos, É. (2003). "Maximizing the spread of influence through a social network".Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '03.p. 137.CiteSeerX10.1.1.14.6198.doi:10.1145/956750.956769.ISBN978-1581137378.S2CID207732226.
  10. ^"ELMA BROTHERS MAKE A MARK IN CHEMISTRY AND MATH".30 June 1989.
  11. ^Members and Foreign Associates ElectedArchived2011-05-07 at theWayback Machine,National Academy of Sciences, May 3, 2011.
  12. ^Greuel, Gert-Martin;Hopcroft, John E.;Wright, Margaret H. (June–July 2007)."The Mathematical Work of Jon Kleinberg"(PDF).Notices of the American Mathematical Society.54(6): 740–743.Retrieved2008-01-15.
  13. ^ACM Names Fellows for Computing Advances that Are Transforming Science and SocietyArchived2014-07-22 at theWayback Machine,Association for Computing Machinery,accessed 2013-12-10.
  14. ^Kleinberg, J. (2000). "The small-world phenomenon".Proceedings of the thirty-second annual ACM symposium on Theory of computing - STOC '00.p. 163.doi:10.1145/335305.335325.ISBN978-1581131840.S2CID221559836.
  15. ^Algorithm Design: 9780132131087: Computer Science Books @ Amazon
  16. ^"Jon Kleinberg receives international math prize".
  17. ^Kleinberg, Jon; Easley, David (2010).Networks, Crowds, and Markets: Reasoning About a Highly Connected World.Cambridge, UK: Cambridge University Press.ISBN978-0-521-19533-1.
  18. ^"Cornell CS Faculty Awards".Cornell University.
[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Jon_Kleinberg&oldid=1245483849"