Жон Майкл Клейнберг: Алгоритмдер мен желілердегі ғылыми еңбектері
Jon Kleinberg
Жон Майкл Клейнберг – АҚШ-тық ғалым, алгоритмдер мен желілер сарапшысы. Корнелл университетінің профессоры, Неванлинна жүлдесінің иегері. Компьютер ғылымы.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Американдық компьютерлік ғалым Джон Майкл Клейнберг (1971 жылы туған) – американдық компьютерлік ғалым және Корнелл университетінің компьютерлік ғылымдар мен ақпараттама ғылымдарының Тиш университеті профессоры. Ол алгоритмдер және желілер саласындағы еңбектерімен белгілі. Халықаралық математикалық одақтың Неванлинна сыйлығының иегері.
American computer scientist
Jon Michael Kleinberg (born 1971) is an American computer scientist and the Tisch University Professor of Computer Science and Information Science at Cornell University known for his work in algorithms and networks. He is a recipient of the Nevanlinna Prize by the International Mathematical Union.
Ерте өмір және білім
Джон Клейнберг 1971 жылы Массачусетс штатының Бостон қаласында математика профессоры әкесі мен компьютерлік кеңесші анасының отбасында дүниеге келген. 1993 жылы ол Корнелл университетінен компьютер ғылымдары бакалавры дәрежесін, ал 1996 жылы Массачусетс технология институтынан докторлық дәрежесін алды. Ол сондай-ақ Корнелл университетінің компьютер ғалымы Роберт Клейнбергтің ағасы болып табылады.
Jon Kleinberg was born in 1971 in Boston, Massachusetts to a mathematics professor father and a computer consultant mother. He received a Bachelor of Science degree in computer science from Cornell University in 1993 and a PhD from Massachusetts Institute of Technology in 1996. He is the older brother of fellow Cornell computer scientist Robert Kleinberg.
Мансап
1996 жылдан бері Клейнберг Корнелл университетінің Компьютерлік ғылымдар кафедрасында профессор қызметін атқарады, сонымен қатар IBM Almaden Research Center-де қонақ ғалым болып жұмыс істейді. Оның еңбектері NSF Карьералық сыйлығы, ONR Жас зерттеуші сыйлығы, MacArthur Foundation стипендиясы, Packard Foundation стипендиясы, Sloan Foundation стипендиясы, сондай-ақ Google, Yahoo! және NSF гранттарымен қолдау көрсетілді. Ол Ұлттық инженерлік академиясының және Америка өнер мен ғылым академиясының мүшесі. 2011 жылы АҚШ Ұлттық ғылым академиясына сайланды. 2013 жылы ол Компьютерлік машиналар қауымдастығының феллосы атанды.
Since 1996 Kleinberg has been a professor in the Department of Computer Science at Cornell, as well as a visiting scientist at IBM'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. He is a member of the National Academy of Engineering and the American Academy of Arts and Sciences. In 2011, he was elected to the United States National Academy of Sciences. In 2013 he became a fellow of the Association for Computing Machinery.
Зерттеу
Клейнберг желілердегі жұмысымен ең танымал. Оның ең белгілі үлесі – IBM-де жұмыс істеген кезінде жасалған HITS алгоритмі. HITS – бұл веб-іздеу алгоритмі, ол алгоритмдерде қолданылатын өзіндік векторлық әдістерге негізделген және веб-беттер немесе сайттар көптеген басқалармен байланысты болса ғана емес, сонымен қатар көптеген басқалармен байланыс жасаса да маңызды деп есептелуі керек екенін мойындау арқылы PageRank-тің толыққанды моделі ретінде қызмет етті. Іздеу жүйелерінің өзі көптеген басқа сайттарға сілтеме жасайтындықтан маңызды сайттардың мысалы болып табылады. Клейнберг бұл жалпылау маңызды веб-беттердің екі түрлі класын білдіретінін түсінді, оларды ол «хабтар» және «авторитеттер» деп атады. HITS алгоритмі – гиперсілтемеленген беттер желісіндегі жетекші хабтар мен авторитеттерді автоматты түрде анықтауға арналған алгоритм. Клейнберг сонымен қатар кіші әлем экспериментінің алгоритмдік аспектілеріндегі жұмысымен де танымал. Ол Стэнли Милграмның әйгілі «алты дәреже» атты хат алмасу эксперименті әлеуметтік желілерде адамдар арасында қысқа жолдар бар екенін ғана емес, сонымен қатар адамдар осы жолдарды табуға бейім екенін бірінші болып түсінді – бұл сырттай қарағанда қарапайым байқау, бірақ ол зертене жатқан желілердің құрылымына терең әсер етеді. Клейнберг осы мәселені зерттеген формальды модель – екі өлшемді тор, онда әр түйін тордағы көршілермен қысқа қашықтықтағы байланыстарға (қабырғаларға) және одан әрі қашықтықтағы түйіндермен ұзақ қашықтықтағы байланыстарға ие. Әрбір v түйіні үшін v мен w арасындағы қашықтықтың квадратына пропорционалды ықтималдықпен w түйініне ұзақ қашықтықтағы қабырға қосылады. Бұл d өлшемді торға жалпыланады, онда ықтималдық қашықтықтың d дәрежесіне пропорционалды төмендейді. Клейнберг көптеген мақалалар мен еңбектерді, сондай-ақ компьютерлік алгоритмдерге арналған оқулықты, «Алгоритмдік жобалау» кітабын жазды, оның бірінші басылымын Эва Тардоспен бірге, ал екінші басылымын жеке жазды. Басқа да наградалардың ішінде ол 2005 жылы «гений гранты» деп аталатын MacArthur Foundation Fellowship және 2006 жылы Nevanlinna Prize сыйлығын алды, бұл сыйлық төрт жылда бір рет Филдс медалімен бірге есептеу математикасының ең жоғары наградасы ретінде табыс етіледі. Оның жаңа кітабы «Желілер, көпшілік және нарықтар: жоғары байланысқан әлем туралы ойлау» деп аталады, ол 2010 жылы Кембридж университетінің баспасынан жарық көрді. Корнеллдің Компьютер ғылымдары студенттік қауымдастығы оған 2002 жылы «Жылдың оқытушысы» сыйлығын табыс етті.
Kleinberg is best known for his work on networks. One of his best known contributions is the 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 and served as the full scale model for PageRank 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. 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. 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 and sole authored the second edition. Among other honors, he received a MacArthur Foundation Fellowship also known as the "genius grant" in 2005 and the Nevanlinna Prize 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.