Файл: Изложение Вся основная информация в одной книге Графы, алгоритмы поиска, ранжирования и многое другое.pdf

98 ГЛАВА 5
представить результаты поиска таким образом, чтобы они выводились в по- рядке их актуальности: сначала должны идти страницы, которые имеют са- мое прямое отношение к нашему запросу, а затем то, что может нас не заин- тересовать. Если вам интересны факты, связанные с изменением климата, в числе первых результатов следует ожидать страницы, принадлежащие ООН,
NASA или «Википедии». Вы, наверное, удивились бы, увидев в качестве пер- вого результата веб-страницу с описанием того, что на эту тему думают члены
Общества плоской Земли. Из тех сотен миллионов страниц, которые могут относиться к вашему запросу, многие окажутся малоинформативными или слишком многословными, но при этом содержащие сущую чепуху. Очевидно, вам захочется сосредоточиться на достоверной информации, которая отно- сится к делу.
Когда на сцене появилась поисковая система Google (автор родился до- статочно давно, чтобы застать этот момент), люди (включая автора) стали переходить на нее с более старых и уже несуществующих систем, так как она выдавала лучшие результаты и делала это быстрее. На руку компании Google сыграло и то, что ее веб-страница была простой и содержала только нужную информацию, хотя в то время зачастую использовали всевозможные брос- кие элементы. Второй фактор оказался весьма поучительным (в Google по- нимали, что пользователям нужны качественные и быстрые поисковые ре- зультаты, а не всякие прибамбасы), но мы сосредоточим наше внимание на первом. Как Google удалось превзойти конкурентов по качеству результа- тов и скорости их выдачи?
Если бы Интернет был небольшим, мы могли бы поручить группе редак- торов составить его каталог и назначить его записям (веб-страницам) раз- ные степени важности. Но масштаб Интернета делает такой подход невоз- можным, хотя попытки этого предпринимались, пока не стало очевидно, что это непосильная задача.
Интернет состоит из веб-страниц, связанных между собой так называе- мыми гиперссылками; текст, содержащий перекрестные ссылки на другие свои участки или внешние документы, называется гипертекстом. Понятие гипертекста предшествовало появлению Всемирной паутины. Описание си- стемы для организации знаний путем взаимного связывания документов впервые предложил американский инженер Вэнивар Буш в 1945 году в жур- нале Atlantic. Всемирную паутину, или просто веб, как ее позже начали назы- вать, разработал британский ученый в области информатики Тим Бернерс-Ли в 1980-х. Бернерс-Ли работал в CERN, Европейской организации по ядер- ным исследованиям, рядом с Женевой, Швейцария, и хотел создать систему,

Если вам интересны факты, связанные с изменением климата… вы, наверное, удивились бы, увидев в качестве первого результата веб-страницу с описанием того, что на эту тему думают члены Общества плоской
Земли.

100 ГЛАВА 5
которая помогла бы ученым обмениваться документами и информацией.
Они могли делать свои документы доступными онлайн и ссылаться в них на другие документы, тоже доступные онлайн. Веб начал и до сих пор про- должает развиваться естественным образом за счет того, что люди добавляют новые веб-страницы. Авторы этих страниц добавляют ссылки на существую- щие страницы, которые имеют к ним какое-то отношение.
Представьте, что вы написали и разместили онлайн статью, в которой проводится краткий обзор эффектов изменения климата в вашей стране.
Было бы неплохо, если бы читатель мог перейти на веб-страницу, которая, по вашему мнению, является достоверным источником на данную тему. По- этому вы добавили в свою статью соответствующую ссылку. Таким образом вы помогаете своим читателям, позволяя им ознакомиться с более глубоким материалом, и в то же время делаете собственную работу более солидной, подкрепляя свои утверждения информацией с веб-страницы, которой дове- ряете.
Но есть много других людей, которые тоже пишут статьи об эффектах изменения климата в своих странах или регионах. И все они тоже хотят со- слаться на достоверный, по их мнению, источник. Таким образом все эти он- лайн-статьи будут содержать гиперссылки, указывающие на подходящие ис- точники информации.
Причина, по которой NASA может выводиться на первом месте при по- иске «изменения климата», связана с тем, что множество авторов, пишущих собственные статьи, решили разместить у себя гиперссылку на веб-страницу
NASA, посвященную этой теме. Авторы приняли это решение независимо друг от друга, но многие из них, скорее всего, сослались на одну и ту же стра- ницу (например, на страницу веб-сайта NASA). Поэтому данную страницу ло- гично считать важной по отношению к другим веб-страницам.
Вся система работает по принципу демократии. Авторы одних веб-стра- ниц ссылаются на другие. Чем больше ссылок указывает на страницу, тем бо- лее важной она считается, тем больше причин на нее сослаться, и тем важнее она в итоге становится.
Но у этого подхода есть одно концептуальное отличие от того, как мы практикуем демократию. Не все написанные статьи равны. Некоторые из них публикуются на более престижных веб-сайтах, чем другие. Статья в блоге, прочитанная горсткой людей, имеет меньший вес, чем статья в онлайн-из- дании с сотнями тысяч читателей. Из этого следует, что для оценки важно- сти веб-страницы следует учитывать не только количество ссылок, которые на нее ведут. Большую роль также играет то, кто именно на нее ссылается.

Вся система работает по принципу демократии.
Авторы одних веб-страниц ссылаются на другие. Чем больше ссылок указывает на страницу, тем важнее она в итоге становится.

102 ГЛАВА 5
Было бы разумно предположить, что ссылка в престижном издании является более весомой, чем ссылка, размещенная на малоизвестном сайте. Конечно, не стоит судить книгу по обложке, но одобрение от выдающегося автора зна- чит больше, чем положительный отзыв неизвестного рецензента. Каждая ссылка — это своего рода одобрение, выраженное одной страницей в отно- шении к другой, и весомость этого одобрения зависит от статуса его автора.
В то же время, если страница ссылается на множество других источников, ее одобрение должно быть поделено между ними.
Набор страниц, связанных гиперссылками, составляет огромный граф, содержащий миллиарды страниц и еще большее количество ссылок между ними. Каждая веб-страница выступает узлом этого графа. Каждая ссылка из одной страницы на другую является направленным ребром. Фундамен- тальной особенностью PageRank было то, что по причинам, которые мы только что описали, структуру этого веб-графа можно использовать для опре- деления важности каждой веб-страницы. Если быть более точным, каждой странице присваивается число — рейтинг, который определяет, насколько она важна относительно других веб-страниц. Чем важнее страница, тем выше ее рейтинг. Алгоритм PageRank применяет этот принцип в грандиозных мас- штабах — в графе, который представляет весь веб.
Основные принципы
Зайдя на любую веб-страницу, можно увидеть ссылки на другие ресурсы, имеющие какое-то отношение к текущему. Само наличие ссылки говорит о важности веб-страницы, на которую он ведет, иначе автор просто не доба- вил бы ее на свой сайт. Взгляните на следующий граф, представляющий не- большой набор веб-страниц, ссылающихся друг на друга.
1 2
3 4
5

PAGERANK 103
Ссылки такого графа, указывающие на веб-страницы, называются обрат-
ными; поэтому мы будем также называть обратными ссылками страницы, на которых они размещены. Таким образом, обратные ссылки веб-страницы 3 являются ребрами, которые ведут к ней (входными ребрами), а также узлами, из которых они исходят: веб-страницы 2, 4 и 5. В этой главе нас интересуют графы, состоящие из веб-страниц, поэтому термины «узел» и «страница» бу- дут взаимозаменяемыми.
Мы создадим алгоритм для определения важности каждой веб-страницы, основанный на следующих двух принципах.
1. Важность веб-страницы зависит от важности тех страниц, которые на нее ссылаются, то есть от важности ее обратных ссылок.
2. Веб-страница разделяет свою важность поровну между страницами, на которые она ссылается.
Представьте, что нам нужно определить важность страницы 3. Мы знаем, что у нее есть обратные ссылки 2, 4 и 5. Возьмем по очереди каждую из них и предположим, что нам известна их важность. Страница 2 разделяет свою важность между страницами 3 и 5; следовательно, странице 3 отводится только половина. Страница 4 тоже разделяет свою важность между двумя страницами, 3 и 1, поэтому странице 3 достается половина ее важности. Нако- нец, страница 5 разделяет свою важность между страницами 2, 3 и 4, поэтому страница 3 получает треть ее важности. Чтобы не быть слишком многослов- ными, обозначим важность страницы i как r(P
i
); r от слова rank («рейтинг»).
Таким образом, страница 3 будет иметь следующую важность.
r P
r P
r P
r P
( )
( )
( )
( )
3 2
4 5
2 2
3
=
+
+
В целом, если нам нужно узнать важность определенной веб-страницы, и при этом нам уже известна важность всех ее обратных ссылок, процесс бу- дет довольно простым: важность каждой обратной ссылки нужно разделить на количество веб-страниц, на которые она ссылается, и сложить все полу- ченные результаты.
Вычисление важности — это своего рода конкурс, на котором веб-стра- ницы голосуют друг за друга. Каждая страница имеет голос определенного веса, который она может отдать за важные, по ее мнению, ресурсы. Если она считает важной только один ресурс, ему достается весь ее голос. Если таких

104 ГЛАВА 5
ресурсов несколько, часть голоса достается каждому из них. Таким обра- зом, если веб-страница хочет проголосовать за три важных ресурса, каждый из них получит одну треть ее голоса. Каким ресурсам должна отдать свой го- лос веб-страница? Тем, на которые ведут ее гиперссылки, то есть тем, на ко- торые она ссылается. И чем определяется важность веб-страницы? Важно- стью ее обратных ссылок.
Эти два принципа придают ранжированию веб-страниц ауру демокра- тичности. Нет какой-то одной стороны, которая определяет, что важно, а что нет. Важность веб-страницы зависит от ресурсов, которые на нее ссылаются, и эти ресурсы голосуют своими ссылками. Но, в отличие от настоящих выбо- ров в большинстве стран мира, не все участники имеют одинаковые голоса.
Голос веб-станицы зависит от ее значимости, которая, опять-таки, определя- ется другими веб-страницами.
Это может показаться казуистикой, так как для определения важности веб-страницы нам фактически нужно определить важность ее обратных ссы- лок. Если следовать тому же принципу, то важность каждой обратной ссылки определяется важностью ее собственных обратных ссылок. Этот процесс мо- жет продолжаться сколько угодно, и в итоге мы так и не узнаем, как вычис- лить значимость веб-страницы, с которой все началось. Что еще хуже, мо- жет обнаружиться, что мы ходим по кругу. В нашем примере для вычисления важности страницы 3 нужно определить, насколько важны страницы 2, 4 и 5.
Чтобы вычислить важность страницы 2, нужно знать важность страницы 1
(и 5, но давайте пока оставим это в стороне). Важность страницы 1 опреде- ляется важностью страницы 4, для получения которой нужно знать важность страницы 3. Мы вернулись к тому, с чего начали.

PAGERANK 105 1
2 3
4 5
1 1/2 1/2 1/3 1/3 1/3 1/2 1/2 1/3 1/3 1/3
Страница 1 отдает свой голос странице 2 (единственному ресурсу, на ко- торый она ссылается). Страница 2 разделяет свой голос на две части и отправ- ляет по 1/2 страницам 3 и 5. Страница 3 разделяет свой голос на три части и передает по 1/3 страницам 1, 4 и 5. Страницы 4 и 5 голосуют аналогичным образом.
По окончании голосования каждая страница подсчитает итоговую сумму голосов (или их частей), которые она получила от своих обратных ссылок. На- пример, страница 1, получившая голоса от страниц 3 и 4, будет иметь 1/2 +
1/3 = 5/6 голоса, а страница 3, получившая голоса от страниц 2, 4 и 5, будет иметь 1/2 + 1/2 + 1/3 = 4/3 голоса. Мы видим, что изначальная доля голо- сов страницы 1 уменьшилась, а у страницы 3 она увеличилась.
Давайте немного изменим условия и выдадим каждой странице перед началом голосования не один голос, а 1/5, чтобы в сумме получалась еди- ница. В целом, если у нас есть n страниц, каждая из них получает 1/n голоса.
В остальном процесс не меняется. Общая важность снова распределяется рав- номерно между всеми веб-страницами, но на этот раз она равна 1.
По окончании голосования важность каждой веб-страницы изменится.
Раньше все они имели одинаковый рейтинг, 1/5 = 0,2, но после вычисле- ний их рейтинги будут следующими (по порядку): 0,17, 0,27, 0,27, 0,13 и 0,17.
Страницы 2 и 3 стали более важными, а страницы 1, 4 и 5 потеряли в значи- мости. Суммарная важность всех веб-страниц равна 1.
Теперь можно начать следующий тур голосования с использованием тех же правил. Страницы распределят собранные ими голоса между ресур- сами, на которые они ссылаются. В конце второго тура каждая страница под- считает свои голоса, чтобы определить собственную относительную значи- мость. После всех вычислений страницы будут иметь такие рейтинги: 0,16,
0,22, 0,26, 0,14 и 0,22.