Четыре результата Джона Клейнберга

Джон Клейнберг получил премию Неванлинны (аналог медали Филдса в теоретической информатике) в 2006 году на Международном математическом конгрессе в Мадриде. В официальном пресс-релизе указано четыре наиболее существенные группы его результатов:
1. Алгоритмы поиска ближайших соседей. Клейнберг предложил новый способ предварительной обработки семейства точек в евклидовом пространстве, позволяющей по новой точке быстро находить ближайшую точку в базе. Впервые удалось построить метод, который доказуемо быстрее, чем полный перебор.
2. Способ определения авторитетности интернет-страниц. Метод, предложенный Клейнбергом основан на вычислении собственного вектора матрицы, описывающей структуру ссылок в вебе. На этих идеях основан алгоритм PageRank, сделавший Google лучшей системой интернет-поиска.
3. Математические модели эффекта «как тесен мир». Джон Клейнберг предложил интересную модель социальной сети с параметром, характеризующим способ создания связей в сети. Ему удалось обнаружить необычное свойство этой модели: существует единственное значение параметра, при котором есть эффективный способ быстро передать сообщение до любого адресата «по цепочке знакомых».
4. Математическая модель «информационных всплесков». В этой работе рассматривается поток некторых информационных сообщений (например, научные статьи, e-mail'ы, новости). Всплеском (burst) называется интервал времени, в который определенное ключевое слово встречается чаще обычного. Кленйберг предложил способ перечислить все всплески, отсортировать их по «весу» и построить их иерархию.