PageRank

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

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

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

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

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

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

Описание

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

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

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

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

История

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

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

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

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

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

Алгоритм

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

Вероятность выражается как числовое значение от 0 до 1. Вероятность 0,5 обычно выражается как "50% шанс" того, что что-то произойдет. Таким образом, документ с PageRank 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 имеет ссылки на все три страницы. Таким образом, при первой итерации страница B передаст половину своего существующего значения (0,125) странице A , а другую половину (0,125) странице C . Страница 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)=\sum _{v\in B_{u}}{\frac {PR(v)}{L(v)}}}$,

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

Коэффициент затухания

Теория PageRank утверждает, что воображаемый серфер, который случайно нажимает на ссылки, в конечном итоге прекратит нажимать. Вероятность того, что на любом этапе человек продолжит следовать ссылкам, является фактором затухания d . Вероятность того, что он вместо этого перейдет на любую случайную страницу, составляет 1 - 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. Утверждение в статье Пейджа и Брина о том, что «сумма всех PageRank равна единице» ^[5] , а также заявления других сотрудников Google ^[32] подтверждают первый вариант приведенной выше формулы.

Пейдж и Брин перепутали эти две формулы в своей самой популярной статье «Анатомия крупномасштабной гипертекстовой поисковой системы в Интернете», где они ошибочно утверждали, что последняя формула формирует распределение вероятностей по веб-страницам. ^[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, поэтому матрица является стохастической (более подробную информацию см. в разделе вычислений ниже). Таким образом, это вариант меры центральности собственного вектора, обычно используемой в сетевом анализе .

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

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

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

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

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

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

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

Вычисление

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

Итеративный

При предполагается начальное распределение вероятностей, обычно ${\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} _{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 }$,

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

Метод мощности

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

Следовательно 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}}|}}}$.

Выполнение

Питон

импортировать  numpy  как  npdef  pagerank ( M ,  d :  float  =  0.85 ): """Алгоритм PageRank с явным числом итераций. Возвращает рейтинг узлов (страниц) в матрице смежности.  Параметры  ----------  M : матрица смежности массива numpy  , где M_i,j представляет собой связь от 'j' к 'i', такую, что для всех 'j'  sum(i, M_i,j) = 1  d : float, необязательный  коэффициент затухания, по умолчанию 0,85 Возвращает  -------  массив numpy  вектор рангов, такой что v_i является i-м рангом из [0, 1], """  N  =  M . shape [ 1 ]  w  =  np . ones ( N )  /  N  M_hat  =  d  *  M  v  =  M_hat  @  w  +  ( 1  -  d )  while ( np . linalg . norm ( w  -  v )  >=  1e-10 ):  w  =  v  v  =  M_hat  @  w  +  ( 1  -  d )  return  vM  =  np . array ([[ 0 ,  0 ,  0 ,  0 ],  [ 0 ,  0 ,  0 ,  0 ],  [ 1 ,  0.5 ,  0 ,  0 ],  [ 0 ,  0.5 ,  1 ,  0 ]]) v  =  pagerank ( M ,  0.85 )

Вариации

PageRank неориентированного графа

PageRank неориентированного графа статистически близок к распределению степеней графа , ^[37] но они, как правило, не идентичны: если — вектор 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}}}$

где обозначает степень вершины , а — множество ребер графа, тогда, при , ^[38] показывает, что: ${\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 для случая ранжирования двух взаимодействующих групп объектов было описано Даугулисом. ^[39] В приложениях может потребоваться моделировать системы, имеющие объекты двух видов, где взвешенное отношение определено на парах объектов. Это приводит к рассмотрению двудольных графов . Для таких графов могут быть определены две связанные положительные или неотрицательные неприводимые матрицы, соответствующие множествам разбиений вершин. Можно вычислить ранжирование объектов в обеих группах как собственные векторы, соответствующие максимальным положительным собственным значениям этих матриц. Нормированные собственные векторы существуют и являются уникальными по теореме Перрона или Перрона–Фробениуса. Пример: потребители и продукты. Вес отношения — это скорость потребления продукта.

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

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

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

Google Toolbar долгое время имела функцию PageRank, которая отображала PageRank посещенной страницы как целое число от 0 (наименее популярный) до 10 (наиболее популярный). Google не раскрывал конкретный метод определения значения PageRank панели инструментов, которое должно было считаться лишь приблизительным указанием ценности веб-сайта. «Toolbar Pagerank» был доступен для проверенных владельцев сайтов через интерфейс Google Webmaster Tools. Однако 15 октября 2009 года сотрудник Google подтвердил, что компания удалила PageRank из своего раздела Webmaster Tools , заявив, что «Мы долго говорили людям, что им не следует так сильно фокусироваться на PageRank. Многие владельцы сайтов, похоже, думают, что это самая важная метрика для отслеживания, что просто не соответствует действительности». ^[41]

«Toolbar Pagerank» обновлялся очень редко. Последнее обновление было в ноябре 2013 года. В октябре 2014 года Мэтт Каттс объявил, что другого видимого обновления Pagerank не будет. ^[42] В марте 2016 года Google объявил, что больше не будет поддерживать эту функцию, а базовый API вскоре прекратит работу. ^[43] 15 апреля 2016 года Google отключил отображение данных PageRank в Google Toolbar, ^[44] хотя PageRank продолжал использоваться внутри компании для ранжирования контента в результатах поиска. ^[45]

Рейтинг SERP

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

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

После введения Google Places в основной органический SERP, на рейтинг компании в Local Business Results, помимо PageRank, повлияло множество других факторов. ^[49] Когда Google подробно рассказал о причинах снижения PageRank на Q&A #March 2016, они объявили Ссылки и Контент главными факторами ранжирования. Ранее в октябре 2015 года RankBrain был объявлен третьим фактором ранжирования, поэтому первые три фактора были официально подтверждены Google. ^[50]

Google каталог PageRank

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

Ложный или поддельный PageRank

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

Манипулирование PageRank

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

В 2019 году Google предложил новый тип тегов, которые не передают PageRank и, таким образом, не имеют ценности для манипуляции ссылками SEO: rel="ugc" как тег для пользовательского контента, такого как комментарии; и тег rel="sponsored" для рекламы или других типов спонсируемого контента. ^[54]

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

Модель направленного серфера

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

Другие применения

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

Научные исследования и академия

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

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

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

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

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

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

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

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

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

Веб-сканер может использовать PageRank как одну из метрик важности, которую он использует для определения того, какой URL посетить во время сканирования сети. Одним из ранних рабочих документов ^[67] , которые использовались при создании Google, является Efficient crawling through URL ordering ^[68], в котором обсуждается использование ряда различных метрик важности для определения того, насколько глубоко и какую часть сайта будет сканировать Google. PageRank представлен как одна из метрик важности, хотя есть и другие, такие как количество входящих и исходящих ссылок для URL и расстояние от корневого каталога на сайте до URL.

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

Другие приложения

В 2005 году в пилотном исследовании в Пакистане, Structural Deep Democracy, SD2 ^{[69] [70]} использовался для выбора лидеров в группе устойчивого сельского хозяйства под названием Contact Youth. SD2 использует PageRank для обработки транзитивных голосов по доверенности с дополнительными ограничениями в виде обязательного назначения не менее двух начальных доверенностей на одного избирателя, и все избиратели являются кандидатами по доверенности. Более сложные варианты могут быть построены поверх SD2, такие как добавление специализированных доверенностей и прямых голосований по конкретным вопросам, но SD2 как базовая зонтичная система требует, чтобы всегда использовались универсальные доверенности.

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

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

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

nofollow

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

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

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

Смотрите также

• Неравенство внимания
• CheiRank
• Домен авторитет
• EigenTrust — децентрализованный алгоритм PageRank
• Гугл-бомбардировка
• Google Колибри
• матрица гугл
• Google Панда
• Google Пингвин
• Поиск Google
• Алгоритм вершины холма
• Центральность Катца – схема 1953 года, тесно связанная с Pagerank
• Создание ссылок
• Поисковая оптимизация
• SimRank — мера сходства объектов, основанная на модели случайного поиска
• Рейтинг доверия
• VisualRank — применение PageRank компанией Google для поиска изображений
• Вебграф

Ссылки

Цитаты

1. "Факты о Google и конкуренции". Архивировано из оригинала 4 ноября 2011 г. Получено 12 июля 2014 г.
2. Салливан, Дэнни (2007-04-26). "Что такое Google PageRank? Руководство для поисковиков и вебмастеров". Search Engine Land . Архивировано из оригинала 2016-07-03.
3. Каттс, Мэтт. «Алгоритмы ранжируют релевантные результаты выше». Архивировано из оригинала 2 июля 2013 г. Получено 19 октября 2015 г.
4. "US7058628B1 - Метод ранжирования узлов в связанной базе данных - Google Patents". Google Patents . Архивировано из оригинала 16 января 2020 г. Получено 14 сентября 2019 г.
5. Брин, С. ; Пейдж, Л. (1998). «Анатомия крупномасштабной гипертекстовой поисковой системы в Интернете» (PDF) . Компьютерные сети и системы ISDN . 30 (1–7): 107–117. CiteSeerX 10.1.1.115.5930 . doi :10.1016/S0169-7552(98)00110-X. ISSN  0169-7552. S2CID  7587743. Архивировано (PDF) из оригинала 27.09.2015. 
6. Gyöngyi, Zoltán; Berkhin, Pavel; Garcia-Molina, Hector; Pedersen, Jan (2006), «Обнаружение спама в ссылках на основе массовой оценки», Труды 32-й Международной конференции по сверхбольшим базам данных (VLDB '06, Сеул, Корея) (PDF) , стр. 439–450, архивировано (PDF) из оригинала 2014-12-03.
7. "FAQ: Все о новом алгоритме Google "Hummingbird"". Search Engine Land . 26 сентября 2013 г. Архивировано из оригинала 23 декабря 2018 г. Получено 18 декабря 2018 г.
8. Ван, Цзыян. «Улучшенные алгоритмы ранжирования веб-страниц на основе ссылок» (PDF) . cs.nyu.edu . Нью-Йоркский университет, кафедра компьютерных наук . Получено 7 августа 2023 г. .
9. Ландау, Эдмунд (1895). «Относительный Wertbemessung der Turnierresultate». Немецкий Вохеншах . 11 (42): 51–54.
10. Зинн, Райнер; Циглер, Гюнтер М. (31.10.2022). «Ландау о шахматных турнирах и PageRank Google». arXiv : 2210.17300 [math.HO].
11. Габриэль Пински и Фрэнсис Нарин (1976). «Влияние цитирования на журнальные совокупности научных публикаций: теория с применением к литературе по физике». Обработка информации и управление . 12 (5): 297–312. doi :10.1016/0306-4573(76)90048-0.
12. Томас Саати (1977). «Метод масштабирования приоритетов в иерархических структурах». Журнал математической психологии . 15 (3): 234–281. doi :10.1016/0022-2496(77)90033-5. hdl : 10338.dmlcz/101787 .
13. Брэдли К. Лав и Стивен А. Сломан. «Изменчивость и детерминанты концептуальной трансформируемости» (PDF) . Труды семнадцатой ежегодной конференции Общества когнитивной науки . стр. 654–659. Архивировано (PDF) из оригинала 23.12.2017 . Получено 23.12.2017 .
14. "Как студент-бакалавриат CogSci изобрел PageRank за три года до Google". bradlove.org. Архивировано из оригинала 2017-12-11 . Получено 2017-12-23 .
15. Ли, Яньхун (6 августа 2002 г.). «К качественной поисковой системе». IEEE Internet Computing . 2 (4): 24–29. doi :10.1109/4236.707687.
16. «Расцвет Baidu (это китайский вариант Google)». The New York Times . 17 сентября 2006 г. Архивировано из оригинала 27 июня 2019 г. Получено 16 июня 2019 г.
17. "About: RankDex" Архивировано 25.05.2015 в Wayback Machine , RankDex ; доступ получен 3 мая 2014 г.
18. USPTO, «Система и метод поиска гипертекстовых документов» Архивировано 05.12.2011 на Wayback Machine , номер патента США: 5920859, изобретатель: Яньхун Ли, дата подачи: 5 февраля 1997 г., дата выпуска: 6 июля 1999 г.
19. Гринберг, Энди, «Человек, который побеждает Google». Архивировано 08.03.2013 в Wayback Machine , журнал Forbes , 5 октября 2009 г.
20. "О: RankDex" Архивировано 2012-01-20 на Wayback Machine , rankdex.com
21. "Метод ранжирования узлов в связанной базе данных". Google Patents. Архивировано из оригинала 15 октября 2015 г. Получено 19 октября 2015 г.
22. Altucher, James (18 марта 2011 г.). «10 необычных вещей о Google». Forbes . Архивировано из оригинала 16 июня 2019 г. Получено 16 июня 2019 г.
23. Грег Виентьес. «Гектор Гарсия-Молина: профессор компьютерных наук Стэнфорда и советник Сергея». стр. минут 25.45-32.50, 34.00–38.20 . Получено 06.12.2019 .
24. Пейдж, Ларри, «PageRank: Bringing Order to the Web» (PDF) . Архивировано (PDF) из оригинала 26 января 2009 г. . Получено 2022-10-06 ., Проект Стэнфордской цифровой библиотеки, беседа. 18 августа 1997 г. (архив 2002 г.)
25. 187-страничное исследование из Университета Граца, Австрия, архивированное 16 января 2014 г. на Wayback Machine , включает примечание о том, что при определении рейтинга страницы в Google также используется человеческий мозг.
26. "Наши продукты и услуги". Архивировано из оригинала 2008-06-23 . Получено 2011-05-27 .
27. Дэвид Вайс и Марк Малсид (2005). История Google . Delacorte Press. стр. 37. ISBN 978-0-553-80457-7.
28. "Google Press Center: Fun Facts". Архивировано из оригинала 2001-07-15.
29. Лиза М. Кригер (1 декабря 2005 г.). «Стэнфорд зарабатывает $336 млн на акциях Google». San Jose Mercury News . Архивировано из оригинала 8 апреля 2009 г. Получено 25 февраля 2009 г. – через цитируется redOrbit.
30. Ричард Брандт. «Starting Up. How Google got its groove». Stanford magazine. Архивировано из оригинала 2009-03-10 . Получено 2009-02-25 .
31. Page, Lawrence ; Brin, Sergey ; Motwani, Rajeev ; Winograd, Terry (1999). Рейтинг цитирования PageRank: наведение порядка в Интернете (отчет). Архивировано из оригинала 27.04.2006., опубликовано в виде технического отчета 29 января 1998 г. PDF Архивировано 18 августа 2011 г. на Wayback Machine
32. Мэтта Каттса : Прямо из Google: что вам нужно знать. Архивировано 7 февраля 2010 г. на Wayback Machine , см. страницу 15 его слайдов.
33. Тахер Хавеливала и Сепандар Камвар (март 2003 г.). "Второе собственное значение матрицы Google" (PDF) . Технический отчет Стэнфордского университета : 7056. arXiv : math/0307056 . Bibcode : 2003math......7056N. Архивировано (PDF) из оригинала 2008-12-17.
34. Gianna M. Del Corso; Antonio Gullí; Francesco Romani (2004). "Быстрое вычисление PageRank с помощью разреженной линейной системы (расширенная аннотация)". В Stefano Leonardi (ред.). Algorithms and Models for the Web-Graph: Third International Workshop, WAW 2004, Рим, Италия, 16 октября 2004 г. Труды . стр. 118–130. CiteSeerX 10.1.1.58.9060 . doi :10.1007/978-3-540-30216-2_10. ISBN  978-3-540-23427-2.
35. Арасу, А.; Новак, Дж.; Томкинс, А.; Томлин, Дж. (2002). «Вычисление PageRank и структура сети: эксперименты и алгоритмы». Труды Одиннадцатой международной конференции World Wide Web, Стендовый доклад . Брисбен, Австралия. С. 107–117. CiteSeerX 10.1.1.18.5264 . 
36. Массимо Франческет (2010). «PageRank: Стоя на плечах гигантов». arXiv : 1002.2858 [cs.IR].
37. Никола Перра и Санто Фортунато; Фортунато (сентябрь 2008 г.). «Спектральные меры центральности в сложных сетях». Phys. Rev. E . 78 (3): 36107. arXiv : 0805.3322 . Bibcode :2008PhRvE..78c6107P. doi :10.1103/PhysRevE.78.036107. PMID  18851105. S2CID  1755112.
38. Винс Гролмуш (2015). «Заметка о PageRank неориентированных графов». Information Processing Letters . 115 (6–8): 633–634. arXiv : 1205.1960 . doi : 10.1016/j.ipl.2015.02.015. S2CID  9855132.
39. Петерис Даугулис; Даугулис (2012). «Заметка об обобщении центральности собственных векторов для двудольных графов и приложений». Networks . 59 (2): 261–264. arXiv : 1610.01544 . doi :10.1002/net.20442. S2CID  1436859.
40. Атиш Дас Сарма; Анисур Рахаман Молла; Гопал Пандуранган; Эли Упфал (2015). «Быстрый распределенный расчет PageRank». Теоретическая информатика . 561 : 113–121. arXiv : 1208.3071 . дои : 10.1016/j.tcs.2014.04.003. S2CID  10284718.
41. Сьюзан Москва. "PageRank Distribution Removed From WMT". Архивировано из оригинала 17 октября 2009 г. Получено 16 октября 2009 г.
42. Бартлман, Вил (2014-10-12). «Обновление рейтинга страниц Google не произойдет». Управляемый администратор. Архивировано из оригинала 2015-04-02 . Получено 2014-10-12 .
43. Шварц, Барри (8 марта 2016 г.). «Google подтвердил, что удаляет Toolbar PageRank». Search Engine Land . Архивировано из оригинала 10 марта 2016 г.
44. Шварц, Барри (18 апреля 2016 г.). "Google Toolbar PageRank официально уходит в тень". Search Engine Land . Архивировано из оригинала 21.04.2016.
45. Саузерн, Мэтт (2016-04-19). "Google PageRank официально закрывает свои двери для публики". Search Engine Journal . Архивировано из оригинала 2017-04-13.
46. Фишкин, Рэнд; Джефф Поллард (2 апреля 2007 г.). "Факторы ранжирования поисковых систем - Версия 2". seomoz.org. Архивировано из оригинала 7 мая 2009 г. Получено 11 мая 2009 г.
47. Довер, Д. Секреты поисковой оптимизации Индианаполис. Wiley. 2011.
48. Виникер, Д. Важность проверки сложности ключевых слов для SEO . Ред. Шварц, М. Digital Guidebook Том 5. News Press. С. 160–164.
49. "Рейтинг листингов: Рейтинг - Справка Google Places". Архивировано из оригинала 2012-05-26 . Получено 2011-05-27 .
50. Кларк, Джек. «Google передает свой прибыльный веб-поиск машинам с искусственным интеллектом». Bloomberg. Архивировано из оригинала 25 марта 2016 г. Получено 26 марта 2016 г.
51. Search Engine Watch: Google Directory был закрыт 25 июля 2011 г.
52. "Как сообщить о платных ссылках". mattcutts.com/blog. 14 апреля 2007 г. Архивировано из оригинала 28 мая 2007 г. Получено 28 мая 2007 г.
53. "Схемы ссылок Google" Архивировано 21.05.2020 на Wayback Machine links
54. "Развивается". Google Developers . Получено 2022-02-08 .
55. "Итак...Вы думаете, что SEO изменилось". 19 марта 2014 г. Архивировано из оригинала 31 марта 2014 г.
56. Мэтью Ричардсон и Педро Домингос, А. (2001). The Intelligent Surfer: Вероятностное сочетание информации о ссылках и контенте в PageRank (PDF) . стр. 1441–1448. Архивировано (PDF) из оригинала 2016-03-04.
57. Gleich, David F. (январь 2015 г.). «PageRank Beyond the Web». Обзор SIAM . 57 (3): 321–363. arXiv : 1407.5107 . doi : 10.1137/140976649. S2CID  8375649.
58. Сенанаяке, Упул; Пиравеенан, Махендра; Зомайя, Альберт (2015). «Индекс Pagerank: выход за рамки количества цитирований при количественной оценке научного влияния исследователей». PLOS ONE . 10 (8): e0134794. Bibcode : 2015PLoSO..1034794S. doi : 10.1371/journal.pone.0134794 . ISSN  1932-6203. PMC 4545754. PMID 26288312  . 
59. G. Ivan & V. Grolmusz (2011). «Когда Интернет встречает клетку: использование персонализированного PageRank для анализа сетей взаимодействия белков». Биоинформатика . 27 (3): 405–7. doi : 10.1093/bioinformatics/btq680 . PMID  21149343.
60. D. Banky и G. Ivan и V. Grolmusz (2013). «Равные возможности для узлов сети с низкой степенью: метод на основе PageRank для идентификации целевых белков в метаболических графах». PLOS ONE . ​​8 (1): 405–7. Bibcode :2013PLoSO...854204B. doi : 10.1371/journal.pone.0054204 . PMC 3558500 . PMID  23382878. 
61. Бернс, Джудит (2009-09-04). "Google trick trackes extinctions". BBC News . Архивировано из оригинала 2011-05-12 . Получено 2011-05-27 .
62. Бенджамин М. Шмидт и Мэтью М. Чингос (2007). «Рейтинг докторских программ по размещению: новый метод» (PDF) . PS: Политология и политика . 40 (июль): 523–529. CiteSeerX 10.1.1.582.9402 . doi :10.1017/s1049096507070771. S2CID  6012229. Архивировано (PDF) из оригинала 2015-02-13. 
63. Йохан Боллен; Марко А. Родригес; Герберт Ван де Сомпель (декабрь 2006 г.). "MESUR: Метрики научного воздействия на основе использования". Труды 7-й совместной конференции ACM/IEEE-CS по цифровым библиотекам . Нью-Йорк: Ассоциация вычислительной техники. arXiv : cs.GL/0601030 . Bibcode : 2006cs........1030B. doi : 10.1145/1255175.1255273. ISBN 978-1-59593-644-8. S2CID  3115544.
64. Флетчер, Джек Маккей; Веннекерс, Томас (2017). «От структуры к активности: использование мер центральности для прогнозирования нейронной активности». Международный журнал нейронных систем . 28 (2): 1750013. doi : 10.1142/S0129065717500137 . hdl : 10026.1/9713 . PMID  28076982.
65. Гупта, Панкадж; Гоэль, Ашиш; Лин, Джимми; Шарма, Аниш; Ван, Донг; Заде, Реза (2013). «WTF: The Who to Follow Service at Twitter». Труды 22-й Международной конференции по всемирной паутине . ACM. С. 505–514. doi :10.1145/2488388.2488433. ISBN 978-1-4503-2035-1. S2CID  207205045 . Получено 11 декабря 2018 г. .
66. Ха, Энтони (2012-05-08). "Y Combinator-Backed Swiftype Builds Site Search That Doesn't Suck". TechCrunch . Архивировано из оригинала 2014-07-06 . Получено 2014-07-08 .
67. "Рабочие документы, касающиеся создания Google". Google . Архивировано из оригинала 28 ноября 2006 г. Получено 29 ноября 2006 г.
68. Чо, Дж.; Гарсия-Молина, Х.; Пейдж, Л. (1998). "Эффективное сканирование через порядок URL". Труды Седьмой конференции по Всемирной паутине . Архивировано из оригинала 2008-06-03.
69. "Yahoo! Groups". Groups.yahoo.com. Архивировано из оригинала 2013-10-04 . Получено 2013-10-02 .
70. "Автопоэтические информационные системы в современных организациях". CiteSeerX 10.1.1.148.9274 . 
71. Зак, Лори; Лэмб, Рон; Болл, Сара (31.12.2012). «Применение PageRank Google к рейтингам НФЛ». Involve: A Journal of Mathematics . 5 (4): 463–471. doi : 10.2140/involve.2012.5.463 . ISSN  1944-4184.
72. Пенья, Хавьер Лопес; Тушетт, Уго (28.06.2012). «Анализ футбольных стратегий с точки зрения сетевой теории». arXiv : 1206.6904 [math.CO].
73. Беггс, Клайв Б.; Шепард, Саймон Дж.; Эммондс, Стейси; Джонс, Бен (2017-06-02). Чжоу, Вэй-Син (ред.). «Новое применение PageRank и алгоритмов пользовательских предпочтений для оценки относительной результативности легкоатлетов на соревнованиях». PLOS ONE . 12 (6): e0178458. Bibcode : 2017PLoSO..1278458B. doi : 10.1371/journal.pone.0178458 . ISSN  1932-6203. PMC 5456068. PMID 28575009  . 
74. B. Jiang (2006). «Ранжирование пространств для прогнозирования движения человека в городской среде». Международный журнал географической информационной науки . 23 (7): 823–837. arXiv : physics/0612011 . Bibcode :2009IJGIS..23..823J. doi :10.1080/13658810802022822. S2CID  26880621.
75. Цзян Б.; Чжао С. и Инь Дж. (2008). «Самоорганизованные естественные дороги для прогнозирования транспортного потока: исследование чувствительности». Журнал статистической механики: теория и эксперимент . P07008 (7): 008. arXiv : 0804.1630 . Bibcode : 2008JSMTE..07..008J. doi : 10.1088/1742-5468/2008/07/P07008. S2CID  118605727.
76. Роберто Навильи, Мирелла Лапата. «Экспериментальное исследование связности графов для неконтролируемого устранения неоднозначности смысла слов» Архивировано 14 декабря 2010 г. на Wayback Machine . Труды IEEE по анализу шаблонов и машинному интеллекту (TPAMI), 32(4), IEEE Press, 2010 г., стр. 678–692.
77. MT Pilehvar, D. Jurgens и R. Navigli. Align, Disambiguate and Walk: A Unified Approach for Measuring Semantic Similarity. Архивировано 01.10.2013 в Wayback Machine . Proc. 51-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL 2013), София, Болгария, 4–9 августа 2013 г., стр. 1341–1351.
78. Андреа Эсули и Фабрицио Себастьяни. "PageRanking WordNet synsets: An Application to Opinion-Related Properties" (PDF) . В трудах 35-го заседания Ассоциации компьютерной лингвистики, Прага, Чехия, 2007, стр. 424–431 . Архивировано (PDF) из оригинала 28 июня 2007 г. . Получено 30 июня 2007 г. .
79. Wang S.; Schreckenberg M.; Guhr T (2023). «Переходы между квазистационарными состояниями в транспортных системах: пример кольцевых автомагистралей Кельна». Журнал статистической механики: теория и эксперимент . 2023 (9): 093401. arXiv : 2302.14596 . Bibcode : 2023JSMTE2023i3401W. doi : 10.1088/1742-5468/acf210 . S2CID  257232659.
80. "Предотвращение спама в комментариях". Google . Архивировано из оригинала 12 июня 2005 г. Получено 1 января 2005 г.
81. "PageRank Sculpting: Parsing the Value and Potential Benefits of Sculpting PR with Nofollow". SEOmoz. 14 октября 2008 г. Архивировано из оригинала 2011-05-14 . Получено 2011-05-27 .
82. "PageRank sculptureing". Mattcutts.com. 2009-06-15. Архивировано из оригинала 2011-05-11 . Получено 2011-05-27 .

Источники

• Альтман, Алон; Моше Тенненхольц (2005). "Системы ранжирования: аксиомы PageRank" (PDF) . Труды 6-й конференции ACM по электронной коммерции (EC-05) . Ванкувер, Британская Колумбия . Получено 29 сентября 2014 г. .
• Ченг, Элис; Эрик Дж. Фридман (2006-06-11). "Manipulability of PageRank under Sybil Strategies" (PDF) . Труды Первого семинара по экономике сетевых систем (NetEcon06) . Энн-Арбор, Мичиган. Архивировано (PDF) из оригинала 2010-08-21 . Получено 2008-01-22 .
• Фарахат, Айман; ЛоФаро, Томас; Миллер, Джоэл К.; Рэй, Грегори; Уорд, Лесли А. (2006). «Рейтинги авторитетности из HITS, PageRank и SALSA: существование, уникальность и влияние инициализации». Журнал SIAM по научным вычислениям . 27 (4): 1181–1201. Bibcode : 2006SJSC...27.1181F. CiteSeerX  10.1.1.99.3942 . doi : 10.1137/S1064827502412875.
• Хавеливала, Тахер; Джех, Глен; Камвар, Сепандар (2003). "Аналитическое сравнение подходов к персонализации PageRank" (PDF) . Технический отчет Стэнфордского университета . Архивировано (PDF) из оригинала 2010-12-16 . Получено 2008-11-13 .
• Лэнгвилл, Эми Н.; Мейер, Карл Д. (2003). «Опрос: глубже внутри PageRank». Интернет-математика . 1 (3).
• Лангвилл, Эми Н .; Мейер, Карл Д. (2006). PageRank Google и не только: наука рейтингов поисковых систем . Princeton University Press. ISBN 978-0-691-12202-1.
• Ричардсон, Мэтью; Домингос, Педро (2002). "Интеллектуальный серфер: вероятностное сочетание информации о ссылках и контенте в PageRank" (PDF) . Труды конференции Advances in Neural Information Processing Systems . Том 14. Архивировано (PDF) из оригинала 28.06.2010 . Получено 18.09.2004 .

Соответствующие патенты

• Оригинальный патент США на PageRank — Метод ранжирования узлов в связанной базе данных. Архивировано 29 августа 2014 г. на Wayback Machine — Номер патента 6 285 999 — 4 сентября 2001 г.
• Патент США PageRank — Метод оценки документов в связанной базе данных — Патент номер 6,799,176 — 28 сентября 2004 г.
• Патент США PageRank — Метод ранжирования узлов в связанной базе данных. Архивировано 28 августа 2019 г. на Wayback Machine — Номер патента 7 058 628 — 6 июня 2006 г.
• PageRank US Patent — Оценка документов в связанной базе данных Архивировано 31.03.2018 на Wayback Machine — Патент номер 7,269,587 — 11 сентября 2007 г.

Внешние ссылки

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