Введение

Американский учёный в области компьютерных наук

Джон Майкл Клейнберг (род. 1971) — американский учёный в области компьютерных наук и профессор компьютерных наук и информатики в Корнелльском университете, известный своими работами в области алгоритмов и сетей. Он является лауреатом премии Неванлинны Международного математического союза.

Ранние годы и образование

Джон Клейнберг родился в 1971 году в Бостоне, штат Массачусетс, в семье профессора математики и консультанта по компьютерным технологиям. Он получил степень бакалавра наук в области компьютерных наук в Корнелльском университете в 1993 году и степень доктора философии в Массачусетском технологическом институте в 1996 году. Он старший брат Роберта Клейнберга, также компьютерного ученого из Корнелла.

Карьера

С 1996 года Клейнберг является профессором кафедры компьютерных наук Корнеллского университета и приглашенным научным сотрудником в Исследовательском центре IBM Almaden. Его работа финансировалась благодаря награде NSF Career Award, награде ONR Young Investigator Award, стипендии Фонда Макартура, стипендии Фонда Паккарда, стипендии Фонда Слоана, а также грантам от Google, Yahoo! и NSF. Он является членом Национальной инженерной академии и Американской академии искусств и наук. В 2011 году он был избран членом Национальной академии наук США. В 2013 году он стал членом Ассоциации вычислительной техники.

Исследования

Клейнберг наиболее известен своими работами в области сетей. Одним из его наиболее известных вкладов является алгоритм HITS, разработанный во время его работы в IBM. HITS – это алгоритм веб-поиска, основанный на методах, использующих собственные векторы, применяемых в алгоритмах, и послуживший полномасштабной моделью для PageRank, поскольку он признает, что веб-страницы или сайты следует считать важными не только в том случае, если на них ссылаются многие другие (как в PageRank), но и в том случае, если они сами ссылаются на многие другие. Поисковые системы сами по себе являются примерами сайтов, важных благодаря большому количеству исходящих ссылок. Клейнберг понял, что это обобщение подразумевает существование двух различных классов важных веб-страниц, которые он назвал «хабами» и «авторитетами». Алгоритм HITS – это алгоритм автоматической идентификации ведущих хабов и авторитетов в сети гиперссылок. Клейнберг также известен своими работами по алгоритмическим аспектам эксперимента «маленького мира». Он одним из первых осознал, что знаменитый эксперимент Стенли Милграма «шесть степеней разделения» с передачей писем подразумевает не только наличие коротких путей между людьми в социальных сетях, но и то, что люди, кажется, умеют находить эти пути – на первый взгляд простое наблюдение, которое, как оказалось, имеет глубокие последствия для структуры рассматриваемых сетей. Формальная модель, в которой Клейнберг изучал этот вопрос, представляет собой двумерную сетку, где каждый узел имеет как связи ближнего радиуса действия (рёбра) с соседними узлами в сетке, так и связи дальнего радиуса действия с узлами, расположенными на большем расстоянии. Для каждого узла v добавляется ребро дальнего радиуса действия между v и другим узлом w с вероятностью, убывающей пропорционально квадрату расстояния между v и w. Это обобщается на d-мерную сетку, где вероятность убывает пропорционально d-й степени расстояния. Клейнберг написал множество статей и монографий, а также учебник по компьютерным алгоритмам «Algorithm Design», первое издание которого было написано в соавторстве с Эвой Тардос, а второе – единолично им. Среди прочих наград он получил стипендию Фонда Макартура, также известную как «гранты для гениев» в 2005 году, и премию Неванлинны в 2006 году – награду, которая вручается раз в четыре года вместе с Филдсовской премией как высшее признание в вычислительной математике. Его новая книга называется «Сети, толпы и рынки: рассуждения о высокосвязанном мире», опубликованная издательством Кембриджского университета в 2010 году. Ассоциация студентов-компьютерщиков Корнеллского университета удостоила его награды «Преподаватель года» в 2002 году.