Рейтинг страницы

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

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

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

В настоящее время PageRank — не единственный алгоритм, используемый Google для упорядочивания результатов поиска, но это первый алгоритм, использованный компанией, и он наиболее известен. По состоянию на 24 сентября 2019 г. срок действия всех патентов, связанных с PageRank, истек.

Описание

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

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

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

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

История

Проблема собственных значений , лежащая в основе алгоритма PageRank, была независимо переоткрыта и повторно использована во многих задачах оценки. В 1895 году Эдмунд Ландау предложил использовать его для определения победителя шахматного турнира. Проблема собственных значений была также предложена в 1976 году Габриэлем Пински и Фрэнсисом Нарином, которые работали над наукометрическим рейтингом научных журналов. в 1977 году Томас Саати в своей концепции процесса аналитической иерархии , которая взвешивала альтернативные варианты, а в 1995 году Брэдли Лавом и Стивеном Сломаном в качестве когнитивной модели концепций — алгоритм центральности.

Поисковая система RankDex от IDD Information Services, разработанная Робином Ли в 1996 году, разработала стратегию оценки сайта и ранжирования страниц. Ли назвал свой механизм поиска «анализом ссылок», который включает в себя ранжирование популярности веб-сайта на основе количества других сайтов, ссылающихся на него. RankDex, первая поисковая система с алгоритмами ранжирования страниц и сайтов, была запущена в 1996 году. Ли подал патент на эту технологию в RankDex в 1997 году; он был предоставлен в 1999 году. Позже он использовал его, когда основал Baidu в Китае в 2000 году. Основатель Google Ларри Пейдж упомянул работу Ли как цитату в некоторых своих патентах на PageRank в США.

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

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

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

Алгоритм

Алгоритм 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.

$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. было три исходящих канала, он перенес бы одну треть По завершении этой итерации страница А будет иметь PageRank примерно 0,458.

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

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

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

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

$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.

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

$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 других страниц. Коэффициент демпфирования корректирует полученное значение в сторону уменьшения. Однако в оригинальной статье была приведена следующая формула, которая привела к некоторой путанице:

$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 равна единице». и претензии других сотрудников Google поддержите первый вариант приведенной выше формулы.

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

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

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

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

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

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

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

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

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

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

$\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}$

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

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

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

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

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

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

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

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

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

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

Вычисление

PageRank можно вычислять итеративно или алгебраически. Итерационный метод можно рассматривать как степенной итерации. метод или силовой метод. Основные выполняемые математические операции идентичны.

Итеративный

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

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

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

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

$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 — коэффициент демпфирования,

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

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

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

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

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

то есть

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

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

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

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

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

Силовой метод

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

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

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

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

до

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

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

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

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

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

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

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

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

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

с

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

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

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

Выполнение

Питон

import numpy as np

def pagerank(M, d: float = 0.85):
    """PageRank algorithm with explicit number of iterations. Returns ranking of nodes (pages) in the adjacency matrix.

    Parameters
    ----------
    M : numpy array
        adjacency matrix where M_i,j represents the link from 'j' to 'i', such that for all 'j'
        sum(i, M_i,j) = 1
    d : float, optional
        damping factor, by default 0.85

    Returns
    -------
    numpy array
        a vector of ranks such that v_i is the i-th rank from [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 v

M = 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 неориентированного графа $G$ статистически близко к распределению степеней графика $G$, но они, как правило, не идентичны: если $R$ — вектор PageRank, определенный выше, и $D$ вектор распределения степеней

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

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

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

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

Ранжирование объектов двух видов

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

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

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

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

На панели инструментов Google уже давно имеется функция PageRank, которая отображает PageRank посещенной страницы в виде целого числа от 0 (наименее популярный) до 10 (наиболее популярный). Google не раскрыл конкретный метод определения значения PageRank панели инструментов, которое следует рассматривать лишь как приблизительный показатель ценности веб-сайта. «Рейтинг панели инструментов» был доступен проверенным администраторам сайта через интерфейс Инструментов Google для веб-мастеров. Однако 15 октября 2009 г. сотрудник Google подтвердил, что компания удалила PageRank из раздела «Инструменты для веб-мастеров» , заявив: «Мы уже давно говорим людям, что им не следует так сильно зацикливаться на PageRank. Многие сайты владельцы, кажется, думают, что это самый важный показатель , который им нужно отслеживать, но это неправда».

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

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

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

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

После появления Google Адресов в основной органической поисковой выдаче на рейтинг компании в результатах местного бизнеса влияет множество других факторов, помимо PageRank. Когда Google подробно рассказал о причинах снижения рейтинга PageRank на конференции Q&A #март 2016 г., они объявили ссылки и контент главными факторами ранжирования. Ранее, в октябре 2015 года, RankBrain был объявлен фактором ранжирования №3, поэтому Google официально подтвердил три главных фактора.

PageRank в каталоге Google

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

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

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

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

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

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

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

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

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

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

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

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

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

PageRank также является полезным инструментом для анализа белковых сетей в биологии.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

nofollow

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

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

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

См. также

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

Ссылки

Источники

• Альтман, Алон; Моше Тенненхольц (2005). «Системы ранжирования: аксиомы PageRank» (PDF) . Материалы 6-й конференции ACM по электронной коммерции (EC-05) . Ванкувер, Британская Колумбия . Проверено 29 сентября 2014 г.
• Ченг, Алиса; Эрик Дж. Фридман (11 июня 2006 г.). «Управление PageRank в рамках стратегий Сивиллы» (PDF) . Материалы первого семинара по экономике сетевых систем (NetEcon06) . Энн-Арбор, Мичиган. Архивировано (PDF) из оригинала 21 августа 2010 г. Проверено 22 января 2008 г.
• Фарахат, Айман; ЛоФаро, Томас; Миллер, Джоэл К.; Рэй, Грегори; Уорд, Лесли А. (2006). «Рейтинги авторитетности на основе HITS, PageRank и SALSA: существование, уникальность и эффект инициализации». SIAM Журнал по научным вычислениям . 27 (4): 1181–1201. Бибкод : 2006ГАК...27.1181Ф . CiteSeerX   10.1.1.99.3942 . дои : 10.1137/S1064827502412875 .
• Хаваливала, Тахер; Эх, Глен; Камвар, Сепандар (2003). «Аналитическое сравнение подходов к персонализации PageRank» (PDF) . Технический отчет Стэнфордского университета . Архивировано (PDF) из оригинала 16 декабря 2010 г. Проверено 13 ноября 2008 г.
• Лэнгвилл, Эми Н .; Мейер, Карл Д. (2003). «Опрос: глубже внутри PageRank». Интернет-математика . 1 (3).
• Лэнгвилл, Эми Н .; Мейер, Карл Д. (2006). PageRank Google и не только: наука о ранжировании в поисковых системах . Издательство Принстонского университета. ISBN  978-0-691-12202-1 .
• Ричардсон, Мэтью; Домингос, Педро (2002). «Интеллектуальный серфер: вероятностное сочетание информации о ссылках и контенте в PageRank» (PDF) . Труды о достижениях в области нейронных систем обработки информации . Том. 14. Архивировано (PDF) из оригинала 28 июня 2010 г. Проверено 18 сентября 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 — Оценка документов в связанной базе данных. Архивировано 31 марта 2018 г. на Wayback Machine — Патент номер 7 269 587 — 11 сентября 2007 г.

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

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