Премия Test Of Time за классическую статью о структуре Интернета в виде галстука-бабочки


Исследователи, чьи работы выявили структуру сети «галстук-бабочку» и, таким образом, улучшили поисковые системы, были награждены третьей Сеульской наградой «Испытание временем» на конференции World Wide Web в этом месяце, проходившей в Перте, Австралия.

Дама Венди Холл, председатель WWW2017, Перт; Профессор Чин-Ван Чунг, сопредседатель WWW2014 Сеул; Андрей Бродер, Рави Кумар и Эндрю Томкинс.

Премия Seoul Test of Time Award, учрежденная и финансируемая учеными-компьютерщиками, которые организовали конференцию World Wide Web в Сеуле в 2014 году, вручается авторам предыдущего документа конференции World Wide Web, который продемонстрировал важные научные, технические или социальные влияние на протяжении многих лет.

В этом году работа Андрея Бродера, Рави Кумара, Фарзина Магула, Прабхакара Рагхавана, Шридхара Раджагопалана, Рэйми Стата, Эндрю Томкинса и Джанет Винер была впервые представлена в 2000 году на 9-й Всемирной всемирной конференции. конференция в Амстердаме.

Согласно сообщению в блоге Google Reseach, в котором объявляется награда:

На момент публикации он получил награду Best Paper Award от конференции WWW и в последующие 17 лет оказался очень влиятельным, собрав более 3500 цитирований.

Хотя Google претендует на это признание, поскольку в настоящее время на него работают пять авторов, в то время Андрей Бродер работал с Altavista, где экспериментальные данные были собраны в 1999 году, а четверо авторов, включая Рави Кумара и Эндрю Томкинса, работали в IBM.

Этот документ внес два важных вклада в понимание структуры Интернета.

Во-первых, его крупномасштабные эксперименты показали, что веб-узлы распределены по степенному закону. То есть вероятность того, что веб-узел имеет i входящих ссылок, примерно пропорциональна 1 / i ^ 2,1.

Во-вторых, в отличие от предыдущих исследований, которые предполагали, что Интернет почти полностью связан, в нем описана гораздо более сложная структура Интернета, которая с тех пор изображается в виде знаковой формы «галстук-бабочка»:

В статье описаны несколько характерных классов веб-страниц:

сильно связанный основной компонент, где каждая страница доступна с любой другой страницы,

так называемые кластеры IN и OUT, которые имеют только однонаправленные пути к ядру или от него,

усики, свисающие с двух кластеров, и трубки, соединяющие кластеры в обход ядра, и, наконец,

отключенные компоненты, которые изолированы от остальной части графа.

В то время как основной компонент полностью подключен и к каждому узлу можно получить доступ из любого другого узла, Broder et al. обнаружили, что в целом Интернет гораздо более слабо связан, чем считалось ранее, в то время как вероятность того, что любые две заданные страницы могут быть достигнуты друг из друга, составляет чуть менее 1/4.

Менее формально. В документе показано, как веб-страницы, связанные друг с другом, распадаются на четыре примерно равные группы, причем страницы в центре сети, узел в галстуке-бабочке, все связаны друг с другом цепочкой ссылок. Страницы, которые ссылались только на ядро, такие как новые страницы, были одной стороной галстука-бабочки. С другой стороны, были страницы, на которых не было ссылок на другие страницы, как на многих корпоративных веб-сайтах. Остальная часть сети не была связана с ядром.

Выступая перед прессой после презентации, Эндрю Томкинс сказал, что результаты работы стали неожиданностью для исследователей:

«Мы не осознавали, что такая большая часть Интернета недоступна для поисковых роботов»,

и продолжил объяснять, как исследование показало, что поисковые роботы, программы, которые постоянно просматривают Интернет, переходят по ссылкам с одной страницы на другую, чтобы поддерживать поисковые системы в актуальном состоянии, которые запускаются только в одном месте, никогда не могут проиндексировать все.

Спустя семнадцать лет после публикации, этот документ рассматривается как основополагающее введение в графовую структуру сети «галстук-бабочку». Такая же структура была обнаружена во многих других крупномасштабных графиках, начиная от цитат из Википедии и заканчивая сетями межбанковских кредитов. Он обеспечивает математическую основу для сканирования и индексации веб-страниц, которая все еще используется, а его теоретические основы изучаются на курсах веб-поиска и интеллектуального анализа данных по всему миру.

Вручая награду, председатель конференции WWW Дам Венди Холл сказала:

«Невозможно переоценить реальное значение этой статьи. Это было первое крупномасштабное эмпирическое исследование динамики Интернета; без этого современные поисковые системы, на которые мы полагаемся, не смогли бы постоянно улучшать свои результаты поиска. Для нас большая честь вручить награду Seoul Test of Time Award 2017 команде, чья работа оказала огромное влияние не только на сообщество World Wide Web, но и на бизнес, научные круги и общество в целом ».

Это был третий раз, когда она вручала награду.

В 2015 году первый получил Сергей Брин и Ларри Пейдж за «Анатомию крупномасштабной гипертекстовой поисковой системы», первоначально представленную на WWW1998 в Брисбене, и именно Андрей Бродер принял участие от их имени, см. Основатели Google. Выиграйте награду “Новое испытание временем”,

В прошлом году получателями были Джордж Карипис, Джозеф Констан, Джон Ридл и Бадрул Сарвар за их доклад «Рекомендуемые алгоритмы совместной фильтрации на основе элементов», первоначально представленный на WWW2001 в Гонконге.


Добавить комментарий