PageRank

Математический рейтинг страницы для простой сети выражается в процентах. (Google использует логарифмическую шкалу .) Страница C имеет более высокий PageRank, чем страница E, хотя на C меньше ссылок; одна ссылка на C происходит с важной страницы и, следовательно, имеет большую ценность. Если пользователи Интернета, которые начинают со случайной страницы, имеют 85% -ную вероятность выбора случайной ссылки со страницы, которую они в данный момент посещают, и 15% -ную вероятность перехода на страницу, выбранную случайным образом из всей сети, они попадут на страницу E 8,1% случаев. (Вероятность перехода на произвольную страницу 15% соответствует коэффициенту демпфирования85%.) Без демпфирования все пользователи сети в конечном итоге оказались бы на страницах A, B или C, а все остальные страницы имели бы нулевой PageRank. При наличии демпфирования страница A фактически ссылается на все страницы в сети, даже если у нее нет собственных исходящих ссылок.

PageRank ( PR ) - это алгоритм, используемый поиском Google для ранжирования веб-страниц в результатах поиска . PageRank - это способ измерения важности страниц веб-сайта. Согласно Google:

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

В настоящее время PageRank - не единственный алгоритм, используемый Google для упорядочивания результатов поиска, но это первый алгоритм, который использовался компанией, и он является наиболее известным. ^{[2] [3]} С 24 сентября 2019 г. истек срок действия PageRank и всех связанных патентов. ^[4]

Описание [ править ]

PageRank - это алгоритм анализа ссылок , который присваивает числовой вес каждому элементу набора документов с гиперссылками , такого как World Wide Web , с целью «измерения» его относительной важности в этом наборе. Алгоритм может быть применен к любой коллекции объектов с взаимными цитатами и ссылками. Числовой вес, который он присваивает любому заданному элементу E , называется PageRank элемента E и обозначается${\ displaystyle PR (E).}$

Результаты PageRank из математического алгоритма , основанный на webgraph , созданный всех World Wide Web - страницах , как узлы и гиперссылка как кромки, принимая во внимание концентраторов власти , таких как cnn.com или mayoclinic.org . Значение рейтинга указывает на важность конкретной страницы. Гиперссылка на страницу считается голосом поддержки. PageRank страницы определяется рекурсивно и зависит от количества и метрики PageRank всех страниц, которые ссылаются на нее (« входящие ссылки »). Страница, на которую ссылаются многие страницы с высоким PageRank, сама получает высокий рейтинг.

После выхода оригинальной статьи Пейджа и Брина было опубликовано множество научных статей, касающихся PageRank . ^[5] На практике концепция PageRank может быть уязвима для манипуляций. Было проведено исследование для определения рейтинга PageRank, на который ложно повлияли. Цель состоит в том, чтобы найти эффективные средства игнорирования ссылок из документов с ложно измененным PageRank. ^[6]

Другие алгоритмы ранжирования на основе ссылок для веб-страниц включают алгоритм HITS, изобретенный Джоном Клейнбергом (используемый Teoma, а теперь и Ask.com ), проект IBM CLEVER , алгоритм TrustRank и алгоритм Hummingbird . ^[7]

История [ править ]

Проблема собственных значений была предложена в 1976 году Габриэлем Пински и Фрэнсисом Нарином, которые работали над наукометрическим рейтингом научных журналов ^[8], в 1977 году Томасом Саати в его концепции аналитического процесса иерархии, который взвешивал альтернативные варианты выбора, ^[9] и в 1995 году Брэдли. Лав и Стивен Сломан как когнитивная модель концепций, алгоритм центральности. ^{[10] [11]}

Поисковая машина под названием " RankDex " от IDD Information Services, разработанная Робином Ли в 1996 году, разработала стратегию оценки сайтов и ранжирования страниц. ^[12] Ли называл свой механизм поиска «анализом ссылок», который включал ранжирование популярности веб-сайта на основе того, сколько других сайтов на него ссылались. ^[13] RankDex, первая поисковая система с алгоритмами ранжирования страниц и рейтинга сайтов, была запущена в 1996 году. ^[14] Ли запатентовал технологию в RankDex, его патент был подан в 1997 году и выдан в 1999 году. ^[15] Позже он использовал его, когда основал Baidu в Китае в 2000 году. ^{[16] [17]} Основатель Google Ларри Пейджсослался на работу Ли как на ссылку в некоторых своих патентах США на PageRank. ^{[18] [14] [19]}

Ларри Пейдж и Сергей Брин разработали PageRank в Стэнфордском университете в 1996 году в рамках исследовательского проекта, посвященного поисковой системе нового типа. Интервью с Эктором Гарсиа-Молиной, профессором Стэнфордских компьютерных наук и советником Сергея ^[20], дает представление о разработке алгоритма ранжирования страниц. ^[21] Сергей Брин считал, что информацию в Интернете можно упорядочить в иерархии по «ссылочной популярности»: страница занимает более высокое место, поскольку на нее больше ссылок. ^[22] Система была разработана с помощью Скотта Хассана и Алана Стеремберга, оба из которых были названы Пейджем и Брином критически важными для развития Google. ^[5] Раджив Мотвани и Терри Виноград в соавторстве с Пейджем и Брином написали первый документ о проекте, описывающий PageRank и начальный прототип поисковой системы Google , опубликованный в 1998 году. ^[5] Вскоре после этого Пейдж и Брин основали Google Inc. , компания, стоящая за поисковой системой Google. Будучи лишь одним из многих факторов, определяющих рейтинг результатов поиска Google, PageRank продолжает служить основой для всех инструментов веб-поиска Google. ^[23]

Название «PageRank» играет на имени разработчика Ларри Пейджа, а также на концепции веб-страницы . ^{[24] [25]} Слово является товарным знаком Google, и процесс PageRank был запатентован ( патент США 6 285 999 ). Однако патент передан Стэнфордскому университету, а не Google. Google обладает исключительными лицензионными правами на патент Стэнфордского университета. Университет получил 1,8 миллиона акций Google в обмен на использование патента; он продал акции в 2005 году за 336 миллионов долларов. ^{[26] [27]}

На PageRank повлиял анализ цитирования , разработанный Юджином Гарфилдом в 1950-х годах в Университете Пенсильвании, и Hyper Search , разработанный Массимо Маркиори из Университета Падуи . В том же году, когда был введен PageRank (1998), Джон Клейнберг опубликовал свою работу о HITS . Основатели Google цитируют Гарфилда, Маркиори и Клейнберга в своих оригинальных статьях. ^{[5] [28]}

Алгоритм [ править ]

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

Вероятность выражается числовым значением от 0 до 1. Вероятность 0,5 обычно выражается как «50% -ный шанс» того, что что-то произойдет. Следовательно, документ с рейтингом страницы 0,5 означает, что существует 50% -ная вероятность того, что человек, щелкнувший случайную ссылку, будет перенаправлен на указанный документ.

Упрощенный алгоритм [ править ]

Предположим , небольшую вселенную из четырех веб - страниц: A , B , C , и D . Ссылки со страницы на саму себя игнорируются. Множественные исходящие ссылки с одной страницы на другую рассматриваются как одна ссылка. PageRank инициализируется одинаковым значением для всех страниц. В исходной форме PageRank сумма PageRank по всем страницам представляла собой общее количество страниц в Интернете на тот момент, поэтому каждая страница в этом примере будет иметь начальное значение 1. Однако более поздние версии PageRank и В оставшейся части этого раздела предположим, что распределение вероятностей находится между 0 и 1. Следовательно, начальное значение для каждой страницы в этом примере равно 0,25.

PageRank, передаваемый от данной страницы к целям ее исходящих ссылок на следующей итерации, делится поровну между всеми исходящими ссылками.

Если бы единственные ссылки в системе были со страниц B , C и D на A , каждая ссылка передала бы 0,25 PageRank в A при следующей итерации, что в сумме составит 0,75.

${\ Displaystyle PR (A) = PR (B) + PR (C) + PR (D). \,}$

Предположим вместо этого, что страница B имеет ссылку на страницы C и A , страница C имеет ссылку на страницу A , а страница D имеет ссылки на все три страницы. Таким образом, после первой итерации, страница Б будет передавать половину своего существующего значения, или 0,125, на страницу A , а другая половина, или 0,125, на страницу C . Page C будет передавать все существующие значения, 0,25, к единственной странице это ссылки на, A . Поскольку у D было три исходящих ссылки, он передал бы треть своего существующего значения, или приблизительно 0,083, на A.. По завершении этой итерации страница A будет иметь рейтинг PageRank примерно 0,458.

${\ displaystyle PR (A) = {\ frac {PR (B)} {2}} + {\ frac {PR (C)} {1}} + {\ frac {PR (D)} {3}}. \,}$

Другими словами, PageRank, присвоенный исходящей ссылкой, равен собственной оценке PageRank документа, деленной на количество исходящих ссылок L () .

${\ displaystyle PR (A) = {\ frac {PR (B)} {L (B)}} + {\ frac {PR (C)} {L (C)}} + {\ frac {PR (D) } {L (D)}}. \,}$

В общем случае значение PageRank для любой страницы u может быть выражено как:

${\ Displaystyle PR (u) = \ сумма _ {v \ in B_ {u}} {\ frac {PR (v)} {L (v)}}}$,

т.е. значение PageRank для страницы u зависит от значений PageRank для каждой страницы v, содержащейся в наборе B _u (набор, содержащий все страницы, ссылающиеся на страницу u ), деленных на количество L ( v ) ссылок со страницы v .

Коэффициент демпфирования [ править ]

Теория PageRank утверждает, что воображаемый пользователь, который случайно нажимает на ссылки, в конечном итоге перестанет нажимать. Вероятность на любом этапе того, что человек продолжит, является демпфирующим фактором d . В различных исследованиях были проверены различные коэффициенты демпфирования, но обычно предполагается, что коэффициент демпфирования будет установлен около 0,85. ^[5]

Коэффициент демпфирования вычитается из 1 (и в некоторых вариантах алгоритма результат делится на количество документов ( N ) в коллекции), а затем этот член добавляется к произведению коэффициента демпфирования и суммы входящие оценки PageRank. То есть,

${\ displaystyle PR (A) = {1-d \ over N} + d \ left ({\ frac {PR (B)} {L (B)}} + {\ frac {PR (C)} {L ( C)}} + {\ frac {PR (D)} {L (D)}} + \, \ cdots \ right).}$

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

${\displaystyle PR(A)=1-d+d\left({\frac {PR(B)}{L(B)}}+{\frac {PR(C)}{L(C)}}+{\frac {PR(D)}{L(D)}}+\,\cdots \right).}$

Различие между ними в том , что значения PageRank в первой формуле сумме к одному, в то время как во второй формуле каждого PageRank является умноженным на N и сумма становится N . Утверждение в статье Пейджа и Брина о том, что «сумма всех рейтингов страниц равняется единице» ^[5], и утверждения других сотрудников Google ^[29] подтверждают первый вариант приведенной выше формулы.

Пейдж и Брин перепутали две формулы в своей самой популярной статье «Анатомия крупномасштабной гипертекстовой поисковой машины в Интернете», где они ошибочно утверждали, что последняя формула формирует распределение вероятностей по веб-страницам. ^[5]

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

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

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

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

${\displaystyle PR(p_{i})={\frac {1-d}{N}}+d\sum _{p_{j}\in M(p_{i})}{\frac {PR(p_{j})}{L(p_{j})}}}$

где - рассматриваемые страницы, - это набор страниц, на которые ссылаются , - это количество исходящих ссылок на странице , - это общее количество страниц.${\displaystyle p_{1},p_{2},...,p_{N}}$${\displaystyle M(p_{i})}$${\displaystyle p_{i}}$${\displaystyle L(p_{j})}$${\displaystyle p_{j}}$${\displaystyle N}$

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

${\displaystyle \mathbf {R} ={\begin{bmatrix}PR(p_{1})\\PR(p_{2})\\\vdots \\PR(p_{N})\end{bmatrix}}}$

где R - решение уравнения

${\displaystyle \mathbf {R} ={\begin{bmatrix}{(1-d)/N}\\{(1-d)/N}\\\vdots \\{(1-d)/N}\end{bmatrix}}+d{\begin{bmatrix}\ell (p_{1},p_{1})&\ell (p_{1},p_{2})&\cdots &\ell (p_{1},p_{N})\\\ell (p_{2},p_{1})&\ddots &&\vdots \\\vdots &&\ell (p_{i},p_{j})&\\\ell (p_{N},p_{1})&\cdots &&\ell (p_{N},p_{N})\end{bmatrix}}\mathbf {R} }$

где функция смежности - это отношение количества исходящих ссылок со страницы j на страницу i к общему количеству исходящих ссылок страницы j. Функция смежности равна 0, если страница не ссылается на , и нормализована так, что для каждого j${\displaystyle \ell (p_{i},p_{j})}$${\displaystyle p_{j}}$${\displaystyle p_{i}}$

${\displaystyle \sum _{i=1}^{N}\ell (p_{i},p_{j})=1}$,

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

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

Основатели Google в своей оригинальной статье ^[28] сообщили, что алгоритм PageRank для сети, состоящей из 322 миллионов ссылок (внутренних и внешних), сходится с допустимым пределом за 52 итерации. Сходимость в сети половинного размера потребовала примерно 45 итераций. На основе этих данных они пришли к выводу, что алгоритм можно очень хорошо масштабировать и что коэффициент масштабирования для чрезвычайно больших сетей будет примерно линейным , где n - размер сети.${\displaystyle \log n}$

В результате теории Маркова можно показать, что PageRank страницы - это вероятность перехода на эту страницу после большого количества кликов. Это происходит с равным , где этим ожиданием числа кликов (или случайных скачков) требуется , чтобы получить от страницы обратно к себе.${\displaystyle t^{-1}}$${\displaystyle t}$

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

Было предложено несколько стратегий для ускорения вычисления PageRank. ^[31]

Различные стратегии манипулирования PageRank были использованы в согласованных усилиях по повышению рейтинга результатов поиска и монетизации рекламных ссылок. Эти стратегии серьезно повлияли на надежность концепции PageRank, ^{[ цитата необходима ],} цель которой - определить, какие документы действительно высоко ценятся веб-сообществом.

С декабря 2007 года, когда он начал активно наказывать сайты, продающие платные текстовые ссылки, Google боролся с фермами ссылок и другими схемами, предназначенными для искусственного завышения PageRank. То, как Google определяет фермы ссылок и другие инструменты манипулирования PageRank, является коммерческой тайной Google .

Вычисление [ править ]

PageRank можно вычислить итеративно или алгебраически. Итерационный метод можно рассматривать как мощность итерационного метода ^{[32] [33]} или метод питания. Основные выполняемые математические операции идентичны.

Итеративный [ править ]

При предполагается начальное распределение вероятностей, обычно${\displaystyle t=0}$

${\displaystyle PR(p_{i};0)={\frac {1}{N}}}$.

где N - общее количество страниц, а это страница i в момент времени 0.${\displaystyle p_{i};0}$

На каждом временном шаге вычисление, как описано выше, дает

${\displaystyle PR(p_{i};t+1)={\frac {1-d}{N}}+d\sum _{p_{j}\in M(p_{i})}{\frac {PR(p_{j};t)}{L(p_{j})}}}$

где d - коэффициент демпфирования,

или в матричной записи

${\displaystyle \mathbf {R} (t+1)=d{\mathcal {M}}\mathbf {R} (t)+{\frac {1-d}{N}}\mathbf {1} }$,

( 1 )

где и - вектор-столбец длины, содержащий только единицы.${\displaystyle \mathbf {R} _{i}(t)=PR(p_{i};t)}$${\displaystyle \mathbf {1} }$${\displaystyle N}$

Матрица определяется как${\displaystyle {\mathcal {M}}}$

${\displaystyle {\mathcal {M}}_{ij}={\begin{cases}1/L(p_{j}),&{\mbox{if }}j{\mbox{ links to }}i\ \\0,&{\mbox{otherwise}}\end{cases}}}$

т.е.

${\displaystyle {\mathcal {M}}:=(K^{-1}A)^{T}}$,

где обозначает матрицу смежности графа, а - диагональная матрица с исходящими степенями по диагонали.${\displaystyle A}$${\displaystyle K}$

Расчет вероятности выполняется для каждой страницы в определенный момент времени, а затем повторяется для следующего момента времени. Вычисление заканчивается, когда для некоторого небольшого${\displaystyle \epsilon }$

${\displaystyle |\mathbf {R} (t+1)-\mathbf {R} (t)|<\epsilon }$,

т.е. когда предполагается сходимость.

Алгебраический [ править ]

—For (т. Е. В установившемся состоянии ) уравнение ( 1 ) имеет вид${\displaystyle t\to \infty }$

${\displaystyle \mathbf {R} =d{\mathcal {M}}\mathbf {R} +{\frac {1-d}{N}}\mathbf {1} }$.

( 2 )

Решение дается

${\displaystyle \mathbf {R} =(\mathbf {I} -d{\mathcal {M}})^{-1}{\frac {1-d}{N}}\mathbf {1} }$,

с единичной матрицей .${\displaystyle \mathbf {I} }$

Решение существует и уникально для . Это можно увидеть, отметив, что это стохастическая матрица по построению и, следовательно, имеет собственное значение, равное единице, как следствие теоремы Перрона – Фробениуса .${\displaystyle 0<d<1}$${\displaystyle {\mathcal {M}}}$

Метод питания [ править ]

Если матрица является вероятностью перехода, т. Е. Стохастической по столбцу, и является распределением вероятностей (т. Е. , Где - матрица всех единиц), то уравнение ( 2 ) эквивалентно${\displaystyle {\mathcal {M}}}$${\displaystyle \mathbf {R} }$${\displaystyle |\mathbf {R} |=1}$${\displaystyle \mathbf {E} \mathbf {R} =\mathbf {1} }$${\displaystyle \mathbf {E} }$

${\displaystyle \mathbf {R} =\left(d{\mathcal {M}}+{\frac {1-d}{N}}\mathbf {E} \right)\mathbf {R} =:{\widehat {\mathcal {M}}}\mathbf {R} }$.

( 3 )

Следовательно, PageRank является главным собственным вектором . Быстрый и простой способ вычислить это - использовать степенной метод : начиная с произвольного вектора , оператор применяется последовательно, т. Е.${\displaystyle \mathbf {R} }$${\displaystyle {\widehat {\mathcal {M}}}}$${\displaystyle x(0)}$${\displaystyle {\widehat {\mathcal {M}}}}$

${\displaystyle x(t+1)={\widehat {\mathcal {M}}}x(t)}$,

до того как

${\displaystyle |x(t+1)-x(t)|<\epsilon }$.

Обратите внимание, что в уравнении ( 3 ) матрица в правой части скобок может быть интерпретирована как

${\displaystyle {\frac {1-d}{N}}\mathbf {E} =(1-d)\mathbf {P} \mathbf {1} ^{t}}$,

где - начальное распределение вероятностей. В текущем случае${\displaystyle \mathbf {P} }$

${\displaystyle \mathbf {P} :={\frac {1}{N}}\mathbf {1} }$.

Наконец, если есть столбцы только с нулевыми значениями, их следует заменить исходным вектором вероятности . Другими словами,${\displaystyle {\mathcal {M}}}$${\displaystyle \mathbf {P} }$

${\displaystyle {\mathcal {M}}^{\prime }:={\mathcal {M}}+{\mathcal {D}}}$,

где матрица определяется как${\displaystyle {\mathcal {D}}}$

${\displaystyle {\mathcal {D}}:=\mathbf {P} \mathbf {D} ^{t}}$,

с

${\displaystyle \mathbf {D} _{i}={\begin{cases}1,&{\mbox{if }}L(p_{i})=0\ \\0,&{\mbox{otherwise}}\end{cases}}}$

В этом случае два вышеупомянутых вычисления с использованием дают один и тот же PageRank, только если их результаты нормализованы:${\displaystyle {\mathcal {M}}}$

${\displaystyle \mathbf {R} _{\textrm {power}}={\frac {\mathbf {R} _{\textrm {iterative}}}{|\mathbf {R} _{\textrm {iterative}}|}}={\frac {\mathbf {R} _{\textrm {algebraic}}}{|\mathbf {R} _{\textrm {algebraic}}|}}}$.

Реализация [ править ]

Scala / Apache Spark [ править ]

Типичный пример - использование функционального программирования Scala с RDD Apache Spark для итеративного вычисления ранга страницы.^{[34] [35]}

объект  SparkPageRank  {  def  main ( args :  Array [ String ])  {  val  spark  =  SparkSession  . строитель  . appName ( "SparkPageRank" )  . getOrCreate () знач  Iters  =  если  ( арг . длина  >  1 )  арг ( 1 ). toInt  еще  10  знач  линии  =  искра . читать . текстовый файл ( аргументы ( 0 )). rdd  val  links  =  lines . карта {  s  =>  val  parts  =  s . split ( "\\ s +" )  ( части ( 0 ), части ( 1 ))  }. отличный (). groupByKey (). кеш ()  var  ranks  =  ссылки . mapValues ( v  =>  1.0 ) for  ( i  <-  1  to  iters )  {  val  contribs  =  links . вступить ( ряды ). ценности . flatMap {  case  ( urls ,  rank )  =>  val  size  =  urls . размер  URL . map ( url  =>  ( url ,  rank  /  size ))  }  ranks  =  contribs . reduceByKey( _  +  _ ). mapValues ( 0,15  +  0,85  *  _ )  } val  output  =  rank . collect ()  вывод . foreach ( tup  =>  println ( tup . _1  +  "имеет ранг:"  +  tup . _2  +  "." )) искра . stop ()  } }

MATLAB / Octave [ править ]

% Параметр M матрица смежности, где M_i, j представляет ссылку от 'j' к 'i', так что для всех 'j'% sum (i, M_i, j) = 1% Параметр d коэффициент демпфирования% Параметр v_quadratic_error квадратичная ошибка для v% Return v, вектор рангов, такой, что v_i является i-м рангом из [0, 1]функция  [v] = rank2 ( M, d, v_quadratic_error )  N = размер ( M , 2 ); % N равно любой размерности M и количеству документов.    v = rand ( N , 1 );   v = v ./ norm ( v , 1 ); % Теперь это L1, а не L2      last_v = единицы ( N , 1 ) * inf ;     M_hat = ( d . * M ) + ((( 1 - d ) / N ) . * One ( N , N ));             while ( norm ( v - last_v , 2 ) > v_quadratic_error )      last_v = v ;  v = M_hat * v ;     % удалил L2 норму повторного PRконецконец функции% 

Пример кода, вызывающего функцию ранжирования, определенную выше:

М = [ 0 0 0 0 1 ; 0,5 0 0 0 0 ; 0,5 0 0 0 0 ; 0 1 0,5 0 0 ; 0 0 0,5 1 0] ;                              ранг2 ( М , 0,80 , 0,001 )  

Python [ править ]

"" "Алгоритм PageRank с явным количеством итераций.Возвращает ------- ранжирование узлов (страниц) в матрице смежности"" "импортировать  numpy  как  npdef  pagerank ( M ,  num_iterations :  int  =  100 ,  d :  float  =  0.85 ):  "" "PageRank: алгоритм на триллион долларов. Параметры  ----------  M: матрица  смежности массива numpy, где M_i, j представляет собой ссылку от 'j' к 'i', так что для всех 'j'  sum (i, M_i, j) = 1  num_iterations: int, необязательное  количество итераций, по умолчанию 100  d: float, необязательный  коэффициент демпфирования, по умолчанию 0,85 Возвращает  -------  numpy array  вектор рангов, такой что v_i - i-ый ранг из [0, 1],  v суммируется до 1 ""»  Н  =  М . Форма [ 1 ]  v  =  нп . Случайным образом . Рандов ( N ,  1 )  v  =  v  /  пр . Linalg . Норма ( v ,  1 )  M_hat  =  ( д  *  М  +  ( 1  -  d )  /  N )  для  i  в  диапазоне ( num_iterations ): v  =  M_hat  @  v  return  vM  =  np . array ([[ 0 ,  0 ,  0 ,  0 ,  1 ],  [ 0,5 ,  0 ,  0 ,  0 ,  0 ],  [ 0,5 ,  0 ,  0 ,  0 ,  0 ],  [ 0 ,  1 ,  0,5 ,  0 ,  0 ] ,  [ 0 ,  0 ,  0.5 ,  1 ,  0]]) v  =  pagerank ( M ,  100 ,  0.85 )

Для схождения этого примера требуется ≈13 итераций.

Варианты [ править ]

PageRank неориентированного графа [ править ]

PageRank неориентированного графа статистически близко к распределению степени графа , ^[36] , но они , как правило , не идентичны: если вектор PageRank определено выше, и является вектором распределения степеней${\displaystyle G}$${\displaystyle G}$${\displaystyle R}$${\displaystyle D}$

${\displaystyle D={1 \over 2|E|}{\begin{bmatrix}\deg(p_{1})\\\deg(p_{2})\\\vdots \\\deg(p_{N})\end{bmatrix}}}$

где обозначает степень вершины , а - множество ребер графа, то, с , ^[37] показывает, что:${\displaystyle \deg(p_{i})}$${\displaystyle p_{i}}$${\displaystyle E}$${\displaystyle Y={1 \over N}\mathbf {1} }$

${\displaystyle {1-d \over 1+d}\|Y-D\|_{1}\leq \|R-D\|_{1}\leq \|Y-D\|_{1},}$

то есть PageRank неориентированного графа равен вектору распределения степеней тогда и только тогда, когда граф является регулярным, т. е. каждая вершина имеет одинаковую степень.

Обобщение PageRank и центральности собственного вектора для двух видов ранжирования объектов [ править ]

Обобщение PageRank на случай ранжирования двух взаимодействующих групп объектов было описано Даугулисом. ^[38] В приложениях может возникнуть необходимость в моделировании систем, имеющих объекты двух типов, в которых взвешенное отношение определяется на парах объектов. Это приводит к рассмотрению двудольных графов . Для таких графов могут быть определены две связанные положительные или неотрицательные неприводимые матрицы, соответствующие множествам разбиений вершин. Можно вычислить ранжирование объектов в обеих группах как собственные векторы, соответствующие максимальным положительным собственным значениям этих матриц. Нормированные собственные векторы существуют и уникальны по теореме Перрона или Перрона – Фробениуса. Пример: потребители и продукты. Относительный вес - это норма расхода продукта.

Распределенный алгоритм вычисления PageRank [ править ]

Sarma et al. описывают два распределенных алгоритма на основе случайного блуждания для вычисления PageRank узлов в сети. ^[39] Один алгоритм с высокой вероятностью выполняет обходы на любом графе (направленном или неориентированном), где n - размер сети и вероятность сброса ( которая называется коэффициентом демпфирования), используемая при вычислении PageRank. Они также представляют более быстрый алгоритм, который обходится в неориентированных графах. В обоих алгоритмах каждый узел обрабатывает и отправляет несколько битов за раунд, которые являются полилогарифмическими по n, размеру сети.${\displaystyle O(\log n/\epsilon )}$${\displaystyle \epsilon }$${\displaystyle 1-\epsilon }$${\displaystyle O({\sqrt {\log n}}/\epsilon )}$

Панель инструментов Google [ править ]

Панель инструментов Google долго была PageRank функция , которая отображается PageRank посещаемой страницы как целое число от 0 до 10. Наиболее популярных веб - сайтов отображается в PageRank из 10. Наименее показал PageRank 0. Google не раскрывает метод , специфичный для определения значение PageRank панели инструментов, которое следует рассматривать только как приблизительное указание ценности веб-сайта. В марте 2016 года Google объявил, что больше не будет поддерживать эту функцию, и базовый API скоро перестанет работать. ^[40]

Рейтинг в поисковой выдаче [ править ]

Страница результатов поисковой системы (SERP) - это фактический результат, возвращаемый поисковой системой в ответ на запрос по ключевому слову. SERP состоит из списка ссылок на веб-страницы с соответствующими текстовыми фрагментами. Рейтинг веб-страницы в поисковой выдаче относится к размещению соответствующей ссылки в поисковой выдаче, где более высокое размещение означает более высокий рейтинг в выдаче. Рейтинг веб-страницы в поисковой выдаче является функцией не только ее PageRank, но и относительно большого и постоянно корректируемого набора факторов (более 200). ^[41] Поисковая оптимизация (SEO) направлена ​​на влияние на рейтинг в выдаче для веб-сайта или набора веб-страниц.

Позиционирование веб-страницы в выдаче Google по ключевому слову зависит от релевантности и репутации, также известных как авторитет и популярность. PageRank - это показатель Google оценки репутации веб-страницы: он не зависит от ключевого слова. Google использует комбинацию авторитета веб-страницы и веб-сайта для определения общего авторитета веб-страницы, конкурирующей за ключевое слово. ^[42] PageRank домашней страницы веб-сайта - лучший показатель, который Google предлагает для авторитета веб-сайта. ^[43]

После введения Google Places в основную органическую поисковую выдачу, множество других факторов, помимо PageRank, влияют на ранжирование бизнеса в результатах местного бизнеса. ^[44]

Рейтинг страниц в каталоге Google [ править ]

Каталог Google PageRank был измерение 8-блок. В отличие от панели инструментов Google, которая показывает числовое значение PageRank при наведении указателя мыши на зеленую полосу, в каталоге Google отображается только полоса, а не числовые значения. Каталог Google был закрыт 20 июля 2011 г. ^[45]

Ложный или поддельный PageRank [ править ]

В прошлом рейтинг страницы, отображаемый на панели инструментов, можно было легко изменить. Перенаправление с одной страницы на другую посредством ответа HTTP 302 или метатега «Обновить» заставляло исходную страницу получать PageRank целевой страницы. Следовательно, новая страница с PR 0 и без входящих ссылок могла получить PR 10 путем перенаправления на домашнюю страницу Google. Эта методика спуфинга была известной уязвимостью. Спуфинг обычно можно обнаружить, выполнив поиск в Google по URL-адресу источника; если в результатах отображается URL-адрес совершенно другого сайта, последний URL-адрес может представлять собой пункт назначения перенаправления.

Управление PageRank [ править ]

В целях поисковой оптимизации некоторые компании предлагают продавать веб-мастерам ссылки с высоким PageRank. ^[46] Поскольку ссылки со страниц с более высоким PR считаются более ценными, они, как правило, дороже. Покупка рекламы со ссылками на качественных содержательных и релевантных сайтах может быть эффективной и жизнеспособной маркетинговой стратегией, чтобы привлечь трафик и повысить ссылочную популярность веб-мастеров. Тем не менее, Google публично предупредил веб-мастеров, что, если они продают или будут обнаружены, что продают ссылки с целью присвоения PageRank и репутации, их ссылки будут обесценены (игнорируются при расчете PageRank других страниц). Практика покупки и продажи ^[47] активно обсуждается в сообществе веб-мастеров. Google советует веб-мастерам использовать значение атрибута HTML nofollow в рекламных ссылках. По словам Мэтта Каттса , Google обеспокоен тем, что веб-мастера пытаются обмануть систему и тем самым снизить качество и релевантность результатов поиска Google. ^[46]

Модель управляемого серфера [ править ]

Более интеллектуальный пользователь, который вероятностно перескакивает со страницы на страницу в зависимости от содержимого страниц и условий запроса пользователя, которого он ищет. Эта модель основана на зависящей от запроса оценке PageRank страницы, которая, как следует из названия, также является функцией запроса. При получении запроса с несколькими терминами пользователь выбирает элемент в соответствии с некоторым распределением вероятностей , и использует этот термин для определения своего поведения на большом количестве шагов. Затем он выбирает другой термин в соответствии с распределением, чтобы определить его поведение, и так далее. В результате распределение по посещаемым веб-страницам составляет QD-PageRank. ^[48]${\displaystyle Q=\{q1,q2,\cdots \}}$${\displaystyle q}$${\displaystyle P(q)}$

Социальные компоненты [ править ]

Катя Майер рассматривает PageRank как социальную сеть, поскольку она объединяет различные точки зрения и мысли в одном месте. ^[49] Люди заходят на страницу PageRank за информацией, и их засыпают цитатами других авторов, у которых также есть мнение по данной теме. Это создает социальный аспект, где все можно обсудить и собрать, чтобы спровоцировать размышления. Между PageRank и людьми, которые его используют, существуют социальные отношения, поскольку он постоянно адаптируется и изменяется к изменениям в современном обществе. Просмотр отношений между PageRank и индивидуумом с помощью социометрии позволяет глубже взглянуть на возникающую связь.

^[50] Маттео Паскинелли считает, что основание для убеждения в том, что PageRank имеет социальный компонент, лежит в идее экономии внимания.. При экономии внимания ценность придается продуктам, которые привлекают большее внимание человека, и результаты, находящиеся на вершине рейтинга PageRank, привлекают большее внимание, чем результаты на последующих страницах. Следовательно, результаты с более высоким PageRank будут в большей степени проникать в человеческое сознание. Эти идеи могут влиять на принятие решений, а действия зрителя имеют прямое отношение к PageRank. Они обладают более высоким потенциалом для привлечения внимания пользователя, поскольку их местоположение увеличивает экономию внимания, уделяемого сайту. Благодаря этому местоположению они могут получить больше трафика, а на их онлайн-рынке будет больше покупок. PageRank этих сайтов позволяет им доверять, и они могут использовать это доверие для роста бизнеса.

Другое использование [ править ]

Математика PageRank является полностью общей и применима к любому графу или сети в любом домене. Таким образом, PageRank теперь регулярно используется в библиометрии, анализе социальных и информационных сетей, а также для прогнозирования и рекомендации ссылок. Он даже используется для системного анализа дорожных сетей, а также для биологии, химии, нейробиологии и физики. ^[51]

Научные исследования и академия [ править ]

Pagerank недавно использовался для количественной оценки научного влияния исследователей. Базовые сети цитирования и сотрудничества используются в сочетании с алгоритмом ранжирования страниц, чтобы создать систему ранжирования для отдельных публикаций, которая распространяется на отдельных авторов. Показано, что новый индекс, известный как pagerank-index (Pi), более справедлив по сравнению с h-index в контексте многих недостатков, которые демонстрирует h-index. ^[52]

Для анализа белковых сетей в биологии PageRank также является полезным инструментом. ^{[53] [54]}

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

Аналогичное новое использование PageRank - это ранжирование академических докторских программ на основе их записей о размещении их выпускников на должности преподавателей. С точки зрения PageRank, академические отделы связываются друг с другом, нанимая своих преподавателей друг у друга (и у себя). ^[56]

Вариант PageRank недавно был предложен в качестве замены традиционного института научной информации (ISI) импакт - фактор , ^[57] и реализованы в Eigenfactor , а также на SCImago . Вместо того, чтобы просто подсчитывать общее количество цитирований в журнале, «важность» каждой цитаты определяется методом PageRank.

В нейробиологии было обнаружено , что PageRank нейрона в нейронной сети коррелирует с его относительной частотой срабатывания. ^[58]

Использование Интернета [ править ]

Персонализированный PageRank используется Twitter для представления пользователям других учетных записей, на которые они могут захотеть подписаться. ^[59]

Продукт Swiftype для поиска по сайту формирует «PageRank, специфичный для отдельных веб-сайтов», просматривая сигналы важности каждого веб-сайта и устанавливая приоритет контента на основе таких факторов, как количество ссылок с домашней страницы. ^[60]

Роботы могут использовать PageRank в качестве одного из нескольких метрик значения , которое он использует , чтобы определить , какой URL для посещения во время обхода полотна. Один из ранних рабочих документов ^[61] , которые были использованы при создании Google является эффективным сканированием через URL упорядочение , ^[62] , который обсуждается использование целого ряда различных показателей важности , чтобы определить , насколько глубоко и насколько сайт Google будет ползать. PageRank представлен как одна из этих метрик важности, хотя есть и другие перечисленные, такие как количество входящих и исходящих ссылок для URL-адреса и расстояние от корневого каталога на сайте до URL-адреса.

PageRank также может использоваться в качестве методологии для измерения очевидного воздействия сообщества, такого как Blogosphere, на сам Интернет в целом. Таким образом, этот подход использует PageRank для измерения распределения внимания в соответствии с парадигмой безмасштабной сети . ^{[ необходима цитата ]}

Другие приложения [ править ]

В 2005 году в пилотном исследовании в Пакистане « Структурная глубокая демократия» SD2 ^{[63] [64]} использовалась для отбора руководителей в группе устойчивого сельского хозяйства под названием «Контактная молодежь». SD2 использует PageRank для обработки транзитивных голосов по доверенности с дополнительными ограничениями, предусматривающими обязательное использование как минимум двух начальных доверенных лиц на одного избирателя, и все избиратели являются кандидатами по доверенности. На основе SD2 могут быть созданы более сложные варианты, такие как добавление специализированных доверенных лиц и прямое голосование по конкретным вопросам, но SD2 как базовая зонтичная система требует, чтобы всегда использовались универсальные прокси.

В спорте алгоритм PageRank используется для ранжирования результатов: команд Национальной футбольной лиги (НФЛ) США; ^[65] индивидуальные футболисты; ^[66] и спортсмены Бриллиантовой лиги. ^[67]

PageRank использовался для ранжирования мест или улиц, чтобы предсказать, сколько людей (пешеходов или транспортных средств) придут на отдельные места или улицы. ^{[68] [69]} В лексической семантике он использовался для устранения неоднозначности смысла слов , ^[70] семантического сходства , ^[71], а также для автоматического ранжирования синсетов WordNet в зависимости от того, насколько сильно они обладают данным семантическим свойством, таким как положительность или негатив. ^[72]

nofollow [ править ]

В начале 2005 года Google внедрила новое значение « NoFollow », ^[73] для отна атрибута ссылок и анкерных элементов HTML, так что разработчики сайтов и блоггеры могут сделать ссылки , которые Google не будет рассматривать для целей PageRank-они ссылки, которые больше не являются «голосом» в системе PageRank. Отношение nofollow было добавлено в попытке помочь в борьбе со спамодексированием .

Например, раньше люди могли создавать множество сообщений на досках объявлений со ссылками на свой веб-сайт, чтобы искусственно завышать свой PageRank. С помощью значения nofollow администраторы доски сообщений могут изменить свой код, чтобы автоматически вставлять rel = 'nofollow' во все гиперссылки в сообщениях, тем самым предотвращая влияние этих конкретных сообщений на PageRank. Однако этот метод предотвращения также имеет различные недостатки, такие как снижение ценности ссылки в законных комментариях. (См .: Спам в блогах # nofollow )

Пытаясь вручную контролировать поток PageRank между страницами на веб-сайте, многие веб-мастера практикуют так называемое «формирование рейтинга страниц» ^[74] , то есть стратегическое размещение атрибута nofollow на определенных внутренних ссылках веб-сайта с целью воронки. PageRank по отношению к тем страницам, которые веб-мастер считал наиболее важными. Эта тактика использовалась с момента появления атрибута nofollow, но может оказаться неэффективной после того, как Google объявил, что блокирование передачи PageRank с помощью nofollow не перенаправляет этот PageRank на другие ссылки. ^[75]

UGC [ править ]

Теперь Google использует атрибут rel UGC в HTML, который означает пользовательский контент, а значение атрибута ugc рекомендуется для ссылок в пользовательском контенте, например, в комментариях и сообщениях на форуме. [Нужна цитата.]

Прекращение поддержки рейтинга страниц на панели инструментов [ править ]

Оценка PageRank от 0 до 10, называемая "PageRank панели инструментов", когда-то была доступна для проверенных специалистов по обслуживанию сайта через интерфейс Google Webmaster Tools. Однако 15 октября 2009 г. сотрудник Google подтвердил, что компания удалила PageRank из своего раздела инструментов для веб-мастеров , заявив, что «Мы давно говорим людям, что им не следует уделять столько внимания PageRank. Многие сайты владельцы, похоже, думают, что это самый важный показатель, за которым они должны следить, что попросту неверно ". ^[76] Кроме того, индикатор PageRank недоступен в собственном браузере Google Chrome .

Видимый рейтинг страницы обновляется очень редко. Последний раз он обновлялся в ноябре 2013 года. В октябре 2014 года Мэтт Каттс объявил, что другого видимого обновления рейтинга страниц не будет. ^[77]

Несмотря на то, что PageRank панели инструментов менее важен для целей SEO , наличие обратных ссылок с более популярных веб-сайтов продолжает подталкивать веб-страницу к более высокому рейтингу в поиске. ^[78]

Google подробно остановился на причинах прекращения поддержки PageRank на Q&A #March и объявил ссылки и контент главными факторами ранжирования, а в октябре 2015 года RankBrain был объявлен фактором ранжирования №3, поэтому теперь Google официально подтвердил эти 3 фактора. ^[79]

15 апреля 2016 года Google официально отключил отображение данных PageRank на панели инструментов Google. Google объявил о своем намерении убрать оценку PageRank с панели инструментов Google несколькими месяцами ранее. ^[80] Google по-прежнему будет использовать рейтинг PageRank при определении ранжирования контента в результатах поиска. ^[81]

См. Также [ править ]

• Неравенство внимания
• CheiRank
• Авторитет домена
• EigenTrust - децентрализованный алгоритм PageRank
• Гугл бомба
• Google Hummingbird
• Матрица Google
• Google Panda
• Google Penguin
• Поиск Гугл
• Алгоритм Hilltop
• Центральность Каца - схема 1953 года, тесно связанная с рейтингом страниц
• Создание ссылок
• Поисковая оптимизация
• SimRank - мера сходства между объектами на основе модели случайного серфера.
• TrustRank
• VisualRank - приложение Google PageRank для поиска изображений
• Webgraph

Ссылки [ править ]

Цитаты [ править ]

Источники [ править ]

Соответствующие патенты [ править ]

• Исходный патент США PageRank - Метод ранжирования узлов в связанной базе данных - Патент № 6 285 999 - 4 сентября 2001 г.
• PageRank Патент США - Метод оценки документов в связанной базе данных - Патент № 6 799 176 - 28 сентября 2004 г.
• PageRank Патент США - Метод ранжирования узлов в связанной базе данных - Патент № 7 058 628 - 6 июня 2006 г.
• PageRank Патент США - Оценка документов в связанной базе данных - Патент № 7 269 587 - 11 сентября 2007 г.

Внешние ссылки [ править ]

• Алгоритмы от Google
• Наши продукты и услуги от Google
• Как Google находит вашу иголку в стоге сена Интернета, Американское математическое общество

(Google использует логарифмическую шкалу.)