Алгоритмы PageRank и HITS

PageRank и HITS — это алгоритмы анализа ссылок, которые оценивают важность или авторитетность веб-страниц на основе структуры гиперссылочного графа, а не только по содержанию страницы.

Definition

PageRank присваивает каждой странице независимую от запроса оценку важности, равную ее стационарной вероятности в модели случайного веб-серфера, который следует исходящим ссылкам с вероятностью демпфирования и телепортируется в противном случае, в то время как HITS вычисляет для зависимого от запроса подграфа оценки авторитетности для страниц с ценным контентом и оценки хабов для страниц, которые ссылаются на хорошие авторитеты, причем каждая из этих оценок взаимно усиливает другую.

Scope

Эта тема охватывает два основополагающих алгоритма анализа ссылок: PageRank, независимую от запроса меру важности страницы, основанную на модели случайного веб-серфера с телепортацией, и HITS, зависимую от запроса схему, которая вычисляет взаимно усиливающие оценки хабов и авторитетов. Она рассматривает лежащие в основе формулировки случайного блуждания и собственных векторов, роль демпфирования и телепортации, сходимость и варианты, чувствительные к теме. Исключается то, как эти оценки комбинируются с текстовыми признаками в окончательный рейтинг, что относится к ранжированию в веб-поиске.

Core questions

• Как модель случайного веб-серфера определяет PageRank как стационарное распределение?
• Почему для корректного определения PageRank необходим коэффициент демпфирования или телепортации?
• Как оценки хабов и авторитетов в HITS взаимно усиливают друг друга?
• Как эти оценки вычисляются итеративно и когда они сходятся?
• В чем различие между PageRank и HITS в отношении независимости от запроса и зависимости от запроса?

Key concepts

• PageRank
• модель случайного веб-серфера
• коэффициент демпфирования и телепортация
• стационарное распределение / главный собственный вектор
• HITS
• хабы и авторитеты
• оценка, независимая от запроса, против оценки, зависимой от запроса
• степенная итерация и сходимость

Key theories

Модель случайного веб-серфера PageRank

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

Хабы и авторитеты HITS

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

Clinical relevance

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

History

В 1998 и 1999 годах два почти одновременных предложения показали, что гиперссылки кодируют авторитетность: HITS Кляйнберга и PageRank Пейджа и Брина. Независимые от запроса, глобально вычисляемые оценки PageRank оказались хорошо подходящими для веб-масштабного обслуживания и легли в основу ведущей поисковой системы, в то время как HITS повлиял на дистилляцию тем и последующие исследования ранжирования графов.

Key figures

• Larry Page
• Sergey Brin
• Jon Kleinberg
• Rajeev Motwani

Seminal works

• page1999
• kleinberg1999
• brin1998

Frequently asked questions

В чем разница между PageRank и HITS?

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

Почему PageRank нужен коэффициент демпфирования?

Без него случайный веб-серфер мог бы застрять на страницах без исходящих ссылок или в циклах, и стационарное распределение могло бы быть не уникальным или некорректно определенным. Вероятность демпфирования (телепортации) позволяет серферу иногда переходить на случайную страницу, гарантируя уникальную, хорошо определенную оценку.