384:'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.
610:
31:
372:
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
403:
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.
316:. 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
1074:
1069:
708:
1099:
951:
1129:
724:
754:
329:
368:
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
1119:
1114:
1109:
1104:
944:
1054:
878:
585:
325:
293:
152:
74:
782:
1089:
1084:
790:
644:
337:
1094:
820:
684:
937:
261:
321:
308:
Since 1996 Kleinberg has been a professor in the
Department of Computer Science at Cornell, as well as a visiting scientist at
423:
1032:
451:
118:
843:
1124:
1134:
317:
313:
162:
721:
1079:
35:
Kleinberg speaking at the
Cornell/Microsoft Research International Symposium on Self-Organizing Online Communities
915:
407:
Cornell's
Association of Computer Science Undergraduates awarded him the "Faculty of the Year" award in 2002.
659:
Proceedings of the ninth ACM SIGKDD international conference on
Knowledge discovery and data mining - KDD '03
1026:
855:
657:
Kempe, D.; Kleinberg, J.; Tardos, É. (2003). "Maximizing the spread of influence through a social network".
1064:
662:
472:
377:
273:
51:
1059:
521:
396:
97:
894:
667:
477:
277:
249:
984:
826:
690:
547:
490:
387:
Kleinberg has written numerous papers and articles as well as a textbook on computer algorithms,
285:
253:
245:
157:
70:
779:
621:
874:
816:
680:
581:
539:
373:
automatically identifying the leading hubs and authorities in a network of hyperlinked pages.
960:
808:
672:
529:
482:
400:
297:
281:
257:
190:
139:
103:
1014:
918:
786:
728:
381:
349:
30:
525:
978:
805:
Proceedings of the thirty-second annual ACM symposium on Theory of computing - STOC '00
609:
353:
195:
84:
746:
574:
1048:
990:
972:
830:
742:
694:
569:
494:
392:
640:
1020:
551:
427:
112:
780:
ACM Names
Fellows for Computing Advances that Are Transforming Science and Society
276:
to a mathematics professor father and a computer consultant mother. He received a
1002:
361:
463:
Kleinberg, J. M. (1999). "Authoritative sources in a hyperlinked environment".
178:
996:
910:
925:
Four
Results of Jon Kleinberg: a talk for St. Petersburg Mathematical Society
924:
447:
929:
543:
812:
676:
486:
222:
395:
and sole authored the second edition. Among other honors, he received a
365:
364:-based methods used in algorithms and served as the full-scale model for
210:
256:
known for his work in algorithms and networks. He is a recipient of the
916:
Interview with Jon
Kleinberg, ACM Infosys Foundation Award recipient by
871:
Networks, Crowds, and
Markets: Reasoning About a Highly Connected World
600:
296:
in 1996. He is the older brother of fellow
Cornell computer scientist
625:
534:
509:
333:
172:
844:
Algorithm Design: 9780132131087: Computer Science Books @ Amazon.com
376:
Kleinberg is also known for his work on algorithmic aspects of the
604:
933:
357:
309:
289:
248:
and the Tisch University Professor of Computer Science and
360:. HITS is an algorithm for web search that builds on the
1075:
Members of the United States National Academy of Sciences
1070:
2013 fellows of the Association for Computing Machinery
803:
Kleinberg, J. (2000). "The small-world phenomenon".
179:
Approximation algorithms for disjoint paths problems
205:
189:
171:
145:
135:
90:
80:
66:
58:
40:
21:
573:
856:"Jon Kleinberg receives international math prize"
709:"ELMA BROTHERS MAKE A MARK IN CHEMISTRY AND MATH"
399:also known as the "genius grant" in 2005 and the
945:
873:. Cambridge, UK: Cambridge University Press.
352:. One of his best-known contributions is the
8:
1100:Massachusetts Institute of Technology alumni
755:Notices of the American Mathematical Society
731:, National Academy of Sciences, May 3, 2011.
563:
561:
380:. He was one of the first to realize that
952:
938:
930:
608:
330:United States National Academy of Sciences
29:
18:
666:
533:
476:
1130:Recipients of the ACM Prize in Computing
747:"The Mathematical Work of Jon Kleinberg"
745:; Wright, Margaret H. (June–July 2007).
348:Kleinberg is best known for his work on
415:
869:Kleinberg, Jon; Easley, David (2010).
722:Members and Foreign Associates Elected
391:, co-authored the first edition with
326:American Academy of Arts and Sciences
294:Massachusetts Institute of Technology
75:Massachusetts Institute of Technology
7:
791:Association for Computing Machinery
338:Association for Computing Machinery
109:ACM-Infosys Foundation Award (2008)
272:Jon Kleinberg was born in 1971 in
14:
328:. In 2011, he was elected to the
1120:21st-century American scientists
1115:20th-century American scientists
262:International Mathematical Union
1110:21st-century American engineers
1105:20th-century American engineers
397:MacArthur Foundation Fellowship
322:National Academy of Engineering
1:
510:"Navigation in a small world"
452:Mathematics Genealogy Project
1055:American computer scientists
622:Jon Kleinberg's publications
356:, developed while he was at
911:Still the Rebel King -Video
895:"Cornell CS Faculty Awards"
643:author profile page at the
244:(born 1971) is an American
163:IBM Almaden Research Center
48:1971 (age 52–53)
16:American computer scientist
1151:
1090:Cornell University faculty
1085:Nevanlinna Prize laureates
580:. Addison–Wesley, Boston.
1095:Cornell University alumni
968:
508:Kleinberg, J. M. (2000).
201:
128:
28:
628:bibliographic database.
320:. He is a member of the
268:Early life and education
1027:Constantinos Daskalakis
630:(subscription required)
314:Almaden Research Center
793:, accessed 2013-12-10.
378:small world experiment
332:. In 2013 he became a
897:. Cornell University.
813:10.1145/335305.335325
741:Greuel, Gert-Martin;
677:10.1145/956750.956769
487:10.1145/324133.324140
274:Boston, Massachusetts
242:Jon Michael Kleinberg
52:Boston, Massachusetts
45:Jon Michael Kleinberg
607:Bibliography Server
98:MacArthur Fellowship
1125:Simons Investigator
526:2000Natur.406..845K
278:Bachelor of Science
250:Information Science
1135:Network scientists
985:Alexander Razborov
785:2014-07-22 at the
727:2011-05-07 at the
465:Journal of the ACM
286:Cornell University
254:Cornell University
246:computer scientist
158:Cornell University
119:Allen Newell Award
71:Cornell University
1080:MacArthur Fellows
1042:
1041:
880:978-0-521-19533-1
743:Hopcroft, John E.
587:978-0-321-29535-4
239:
238:
130:Scientific career
1142:
961:Nevanlinna Prize
954:
947:
940:
931:
899:
898:
891:
885:
884:
866:
860:
859:
852:
846:
841:
835:
834:
800:
794:
777:
771:
770:
768:
767:
751:
738:
732:
719:
713:
712:
705:
699:
698:
670:
654:
648:
638:
632:
631:
619:
613:
612:
601:Jon M. Kleinberg
598:
592:
591:
579:
576:Algorithm Design
568:Kleinberg, Jon;
565:
556:
555:
537:
535:10.1038/35022643
505:
499:
498:
480:
460:
454:
445:
439:
438:
436:
435:
426:. Archived from
420:
401:Nevanlinna Prize
389:Algorithm Design
298:Robert Kleinberg
282:computer science
258:Nevanlinna Prize
235:
232:
230:
228:
226:
224:
219:
216:
214:
212:
191:Doctoral advisor
185:
140:Computer Science
104:Nevanlinna Prize
33:
19:
1150:
1149:
1145:
1144:
1143:
1141:
1140:
1139:
1045:
1044:
1043:
1038:
1015:Daniel Spielman
964:
958:
923:Yury Lifshits,
919:Stephen Ibaraki
907:
902:
893:
892:
888:
881:
868:
867:
863:
854:
853:
849:
842:
838:
823:
807:. p. 163.
802:
801:
797:
787:Wayback Machine
778:
774:
765:
763:
749:
740:
739:
735:
729:Wayback Machine
720:
716:
711:. 30 June 1989.
707:
706:
702:
687:
661:. p. 137.
656:
655:
651:
647:Digital Library
639:
635:
629:
624:indexed by the
620:
616:
599:
595:
588:
567:
566:
559:
507:
506:
502:
462:
461:
457:
446:
442:
433:
431:
422:
421:
417:
413:
382:Stanley Milgram
346:
306:
270:
221:
220:
209:
183:
167:
124:
73:
54:
49:
47:
46:
36:
24:
17:
12:
11:
5:
1148:
1146:
1138:
1137:
1132:
1127:
1122:
1117:
1112:
1107:
1102:
1097:
1092:
1087:
1082:
1077:
1072:
1067:
1062:
1057:
1047:
1046:
1040:
1039:
1037:
1036:
1033:Mark Braverman
1030:
1024:
1018:
1012:
1006:
1000:
994:
988:
982:
979:Leslie Valiant
976:
969:
966:
965:
959:
957:
956:
949:
942:
934:
928:
927:
921:
913:
906:
905:External links
903:
901:
900:
886:
879:
861:
847:
836:
822:978-1581131840
821:
795:
772:
733:
714:
700:
686:978-1581137378
685:
668:10.1.1.14.6198
649:
633:
614:
593:
586:
557:
500:
478:10.1.1.54.8485
455:
440:
414:
412:
409:
354:HITS algorithm
345:
342:
305:
302:
288:in 1993 and a
269:
266:
237:
236:
207:
203:
202:
199:
198:
196:Michel Goemans
193:
187:
186:
175:
169:
168:
166:
165:
160:
155:
149:
147:
143:
142:
137:
133:
132:
126:
125:
123:
122:
116:
110:
107:
101:
94:
92:
88:
87:
85:HITS algorithm
82:
81:Known for
78:
77:
68:
64:
63:
60:
56:
55:
50:
44:
42:
38:
37:
34:
26:
25:
22:
15:
13:
10:
9:
6:
4:
3:
2:
1147:
1136:
1133:
1131:
1128:
1126:
1123:
1121:
1118:
1116:
1113:
1111:
1108:
1106:
1103:
1101:
1098:
1096:
1093:
1091:
1088:
1086:
1083:
1081:
1078:
1076:
1073:
1071:
1068:
1066:
1065:Living people
1063:
1061:
1058:
1056:
1053:
1052:
1050:
1034:
1031:
1028:
1025:
1022:
1019:
1016:
1013:
1010:
1009:Jon Kleinberg
1007:
1004:
1001:
998:
995:
992:
991:Avi Wigderson
989:
986:
983:
980:
977:
974:
973:Robert Tarjan
971:
970:
967:
962:
955:
950:
948:
943:
941:
936:
935:
932:
926:
922:
920:
917:
914:
912:
909:
908:
904:
896:
890:
887:
882:
876:
872:
865:
862:
857:
851:
848:
845:
840:
837:
832:
828:
824:
818:
814:
810:
806:
799:
796:
792:
788:
784:
781:
776:
773:
761:
757:
756:
748:
744:
737:
734:
730:
726:
723:
718:
715:
710:
704:
701:
696:
692:
688:
682:
678:
674:
669:
664:
660:
653:
650:
646:
642:
641:Jon Kleinberg
637:
634:
627:
623:
618:
615:
611:
606:
602:
597:
594:
589:
583:
578:
577:
571:
564:
562:
558:
553:
549:
545:
541:
536:
531:
527:
523:
520:(6798): 845.
519:
515:
511:
504:
501:
496:
492:
488:
484:
479:
474:
470:
466:
459:
456:
453:
449:
448:Jon Kleinberg
444:
441:
430:on 2012-05-04
429:
425:
419:
416:
410:
408:
405:
402:
398:
394:
390:
385:
383:
379:
374:
371:
367:
363:
359:
355:
351:
343:
341:
339:
335:
331:
327:
323:
319:
315:
311:
303:
301:
299:
295:
291:
287:
283:
279:
275:
267:
265:
263:
259:
255:
251:
247:
243:
234:
218:
211:videolectures
208:
204:
200:
197:
194:
192:
188:
181:
180:
176:
174:
170:
164:
161:
159:
156:
154:
151:
150:
148:
144:
141:
138:
134:
131:
127:
120:
117:
114:
111:
108:
105:
102:
99:
96:
95:
93:
89:
86:
83:
79:
76:
72:
69:
65:
61:
57:
53:
43:
39:
32:
27:
23:Jon Kleinberg
20:
1021:Subhash Khot
1008:
889:
870:
864:
850:
839:
804:
798:
775:
764:. Retrieved
762:(6): 740–743
759:
753:
736:
717:
703:
658:
652:
636:
617:
596:
575:
517:
513:
503:
468:
464:
458:
443:
432:. Retrieved
428:the original
424:"ACM Awards"
418:
406:
388:
386:
375:
369:
347:
307:
271:
241:
240:
177:
146:Institutions
129:
113:Harvey Prize
1060:1971 births
1003:Madhu Sudan
570:Tardos, Éva
362:eigenvector
59:Nationality
1049:Categories
997:Peter Shor
766:2008-01-15
471:(5): 604.
434:2013-05-08
411:References
393:Éva Tardos
280:degree in
217:_kleinberg
831:221559836
695:207732226
663:CiteSeerX
495:221584113
473:CiteSeerX
233:/kleinber
67:Education
783:Archived
725:Archived
572:(2006).
544:10972276
366:PageRank
350:networks
344:Research
324:and the
227:.cornell
62:American
963:winners
552:4425543
522:Bibcode
450:at the
370:link to
336:of the
260:by the
206:Website
1035:(2022)
1029:(2018)
1023:(2014)
1017:(2010)
1011:(2006)
1005:(2002)
999:(1998)
993:(1994)
987:(1990)
981:(1986)
975:(1982)
877:
829:
819:
693:
683:
665:
626:Scopus
584:
550:
542:
514:Nature
493:
475:
334:fellow
304:Career
184:(1996)
182:
173:Thesis
136:Fields
121:(2014)
115:(2013)
106:(2006)
100:(2005)
91:Awards
827:S2CID
750:(PDF)
691:S2CID
548:S2CID
491:S2CID
292:from
284:from
231:/home
875:ISBN
817:ISBN
681:ISBN
605:DBLP
582:ISBN
540:PMID
229:.edu
215:/jon
213:.net
41:Born
809:doi
673:doi
645:ACM
603:at
530:doi
518:406
483:doi
358:IBM
318:NSF
312:'s
310:IBM
290:PhD
252:at
225:.cs
223:www
153:MIT
1051::
825:.
815:.
789:,
760:54
758:.
752:.
689:.
679:.
671:.
560:^
546:.
538:.
528:.
516:.
512:.
489:.
481:.
469:46
467:.
340:.
300:.
264:.
953:e
946:t
939:v
883:.
858:.
833:.
811::
769:.
697:.
675::
590:.
554:.
532::
524::
497:.
485::
437:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
