Jon Michael Kleinberg (geb. 1971) ist ein US-amerikanischer Informatiker und Tisch University Professor für Informatik und Informationswissenschaft an der Cornell University . Er ist bekannt für seine Arbeiten auf dem Gebiet der Algorithmen und Netzwerke. [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] Er ist Träger des Nevanlinna-Preises der Internationalen Mathematischen Union .

Frühes Leben und Bildung

Jon Kleinberg wurde 1971 in Boston, Massachusetts , als Sohn von Eugene Kleinberg, einem Mathematikprofessor an der SUNY Buffalo , und Evelyn Kleinberg, einer Informatikerin, geboren. [ 9 ] [ 10 ] Sein Großvater, Samuel Kleinberg, schloss sein Studium an der Cornell University 1934 ab und unterrichtete Mathematik und Physik an einer High School in Brooklyn. [ 10 ] Er erwarb 1993 einen Bachelor of Science in Informatik an der Cornell University und 1996 einen Doktortitel am Massachusetts Institute of Technology (MIT). Er ist der ältere Bruder des ebenfalls an der Cornell University tätigen Informatikers Robert Kleinberg .

Karriere

Seit 1996 ist Kleinberg Professor am Fachbereich Informatik der Cornell University und Gastwissenschaftler am Almaden Research Center von IBM . Seine Arbeit wurde durch ein NSF Career Award, ein ONR Young Investigator Award, ein Stipendium der MacArthur Foundation, ein Stipendium der Packard Foundation, ein Stipendium der Sloan Foundation sowie durch Fördergelder von Google, Yahoo! und der NSF unterstützt . Er ist Mitglied der National Academy of Engineering und der American Academy of Arts and Sciences . 2011 wurde er in die National Academy of Sciences der Vereinigten Staaten gewählt . [ 11 ] [ 12 ] 2013 wurde er Fellow der Association for Computing Machinery . [ 13 ]

Forschung

Kleinberg ist vor allem für seine Netzwerkforschung bekannt . Einer seiner bekanntesten Beiträge ist der HITS-Algorithmus , den er während seiner Zeit bei IBM entwickelte . HITS ist ein Algorithmus für die Websuche, der auf den in Algorithmen verwendeten Eigenvektormethoden aufbaut und als umfassendes Modell für PageRank diente . Er erkannte, dass Webseiten nicht nur dann als wichtig gelten, wenn sie von vielen anderen verlinkt werden (wie bei PageRank), sondern auch, wenn sie selbst viele Links zu anderen Seiten haben. Suchmaschinen selbst sind Beispiele für Seiten, die aufgrund ihrer vielen Links wichtig sind. Kleinberg erkannte, dass diese Verallgemeinerung zwei verschiedene Klassen wichtiger Webseiten impliziert, die er „Hubs“ und „Autoritäten“ nannte. Der HITS-Algorithmus dient der automatischen Identifizierung der führenden Hubs und Autoritäten in einem Netzwerk von verlinkten Seiten.

Kleinberg ist auch für seine Arbeiten zu algorithmischen Aspekten des Small-World-Experiments bekannt . [ 14 ] Er erkannte als einer der Ersten, dass Stanley Milgrams berühmtes „Sechs-Grade“-Experiment, bei dem er Briefe weitergab, nicht nur kurze Verbindungen zwischen Individuen in sozialen Netzwerken implizierte, sondern auch, dass Menschen diese Verbindungen gut zu finden scheinen – eine scheinbar einfache Beobachtung, die sich als weitreichend für die Struktur der betreffenden Netzwerke erwies. Das formale Modell, in dem Kleinberg diese Frage untersuchte, ist ein zweidimensionales Gitter, in dem jeder Knoten sowohl kurzreichweitige Verbindungen (Kanten) zu benachbarten Knoten als auch langreichweitige Verbindungen zu weiter entfernten Knoten besitzt. Für jeden Knoten v wird eine langreichweitige Kante zwischen v und einem anderen Knoten w mit einer Wahrscheinlichkeit hinzugefügt, die mit der zweiten Potenz der Entfernung zwischen v und w abnimmt. Dies wird auf ein d-dimensionales Gitter verallgemeinert, wo die Wahrscheinlichkeit mit der d-ten Potenz der Entfernung abnimmt.

Kleinberg hat zahlreiche wissenschaftliche Arbeiten und Artikel sowie das Lehrbuch „ Algorithm Design“ über Computeralgorithmen verfasst , das er gemeinsam mit Éva Tardos schrieb . [ 4 ] Unter anderem erhielt er 2005 ein MacArthur-Stipendium, auch bekannt als „Genie-Stipendium“, und 2006 den Nevanlinna-Preis , der alle vier Jahre zusammen mit der Fields-Medaille als höchste Auszeichnung in der Computermathematik verliehen wird . [ 15 ] 2010 veröffentlichte er sein Buch „Networks, Crowds, and Markets: Reasoning About a Highly Connected World“ im Cambridge University Press . [ 16 ]

Die Vereinigung der Informatikstudenten der Cornell University verlieh ihm im Jahr 2002 die Auszeichnung „Fakultät des Jahres“. [ 17 ]

Referenzen

  1. ^ Jon Kleinberg beim Mathematics Genealogy Project
  2. ^ Kleinberg, JM (1999). „Autoritative Quellen in einer hyperverlinkten Umgebung“. Journal of the ACM . 46 (5): 604. CiteSeerX  10.1.1.54.8485 . doi : 10.1145/324133.324140 . S2CID  221584113 .
  3. ^ Kleinberg, JM (2000). „Navigation in einer kleinen Welt“ . Nature . 406 (6798): 845. Bibcode : 2000Natur.406..845K . doi : 10.1038 / 35022643 . PMID 10972276. S2CID 4425543 .  
  4. ^ Kleinberg , Jon ; Tardos, Eva (2006). Algorithmus-Design . Addison-Wesley, Boston. ISBN 978-0-321-29535-4Die
  5. ^ Jon M. Kleinberg auf dem DBLP -Bibliographieserver
  6. ^ Die Publikationen von Jon Kleinberg sind in derbibliografischen Datenbank Scopus indexiert. (Abonnement erforderlich)
  7. ^ Jon Kleinbergs Autorenprofilseite in der ACM Digital Library
  8. 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. CiteSeerX 10.1.1.14.6198 . doi : 10.1145/956750.956769 . ISBN  978-1581137378. S2CID  207732226 .
  9. ^ „ELMA BROTHERS MACHEN SICH IN CHEMIE UND MATHEMATIK EIN ZEUG“ . 30. Juni 1989.
  10. ^ a b "Cornell Alumni Magazine Januar/Februar 2006" . ecommons.cornell.edu .
  11. ^ Mitglieder und ausländische Mitarbeiter gewählt. Archiviert am 07.05.2011 in der Wayback Machine , National Academy of Sciences, 3. Mai 2011.
  12. ^ Greuel, Gert-Martin; Hopcroft, John E .; Wright, Margaret H. (Juni–Juli 2007). „The Mathematical Work of Jon Kleinberg“ (PDF) . Notices of the American Mathematical Society . 54 (6): 740–743 . Abgerufen am 15. Januar 2008 .
  13. ^ ACM ernennt Fellows für Fortschritte in der Computertechnik, die Wissenschaft und Gesellschaft verändern. Archiviert am 22.07.2014 bei der Wayback Machine , Association for Computing Machinery , abgerufen am 10.12.2013.
  14. ^ Kleinberg, J. (2000). „Das Small-World-Phänomen“. Proceedings of the thirty-second annual ACM symposium on Theory of computing - STOC '00 . S. 163. doi : 10.1145/335305.335325 . ISBN 978-1581131840S2CID  221559836 .​
  15. ^ „Jon Kleinberg erhält internationalen Mathematikpreis“ .
  16. ^ Kleinberg, Jon; Easley, David (2010). Netzwerke, Massen und Märkte: Überlegungen zu einer hochvernetzten Welt . Cambridge, UK: Cambridge University Press. ISBN 978-0-521-19533-1Die
  17. ^ „Cornell CS Faculty Awards“ . Cornell University.