Расчет pagerank. Описание PageRank, способы его вычисления

PageRank или пейдж-ранк – один из алгоритмов ссылочного ранжирования в .

Этот показательно может быть от 0 до 10. На базе алгоритма ранжирования PageRank появился Гугл.

Если PageRank дать точное определение то:

PageRank - это числовая величина, характеризующая «важность» веб-страницы. Чем больше ссылок на страницу, тем она становится «важнее». Кроме того, «вес» страницы А определяется весом ссылки, передаваемой страницей B. Таким образом, PageRank - это метод вычисления веса страницы путём подсчёта важности ссылок на неё.

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

Как можно проверить PageRank

Пейдж-ранк можно проверить с помощью разных сервисов или тулбаров в браузерах. Например, у сайта google.com PageRank 9, из 10.

Сервисы для проверки PR :

cy-pr.com
pr-cy.ru

Так де это можно сделать с помощью тулбаров, как:

seoquake.com
developing.ru/seobar
recipdonor.com/bar

Как было сказано ниже, PageRank влияет на ранжирование сайта, и если на продвигаемый сайт будут ссылаться множество ссылок с высоким пейдж-ранк, то это PR вашего сайта вырастет.

Основная формула, которая описывает PR:

Довольно таки обширную статью написал Александр Садовский, про растолкованный PageRank, статью читаем здесь

Книги по Google PageRank

— Google’s PageRank and Beyond: The Science of Search Engine Rankings

Данная книга с кучей формул, и для ее успешного чтения как минимум нужно хорошо знать математику

Часто задают такие вопросы

Как повысить PR сайта?

На самом деле есть много способов это сделать, самый простой и часто распространённый – это поставить ссылки с сайтов, на которых высокий PR, и когда поисковая система учтет ссылки, и сделает обновление алгоритма, он повысится на вашем сайте.

Когда и как часто обновляется PageRank?

Раньше PR обновлялся раз в 3-4 месяца, сейчас он обновляется по-разному, и нет четких интервалов, это может быть 1-3 раза в год.

Это обновление тулбарного (того что мы видим) пейдж-ранк, внутренний PR скорее всего обновляется чаще.

Влияет ли посещаемость сайта на PageRank?

Нет, не влияет. На PageRank влияет количество и качество ссылок, которые ссылаются на сайт.

PageRank – один из алгоритмов ранжирования поисковой системы Google. Чем выше он на вашем сайте, тем лучше.

В поисковой системе.

Одним из первых показателей , основанным на передаче так называемого веса ссылки, стал алгоритм PageRank. Со временем этот алгоритм совершенствовался создателями каждой из , усложнялся и все меньше влиял на общую документа. Однако во все ссылочные алгоритмы поисковиков заложена идея PageRank, созданная в 1996 году Сергеем Брином и Ларри Пейджем, усовершенствованная и усложненная.

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

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

Классическая формула расчета PageRank:

, где

PR - PageRank рассматриваемой страницы,

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

PRi - PageRank i-й страницы, ссылающейся на рассматриваемую страницу,

Ci - общее число ссылок на i-й странице.

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

Сложность прогнозирования PR состоит в том, что в реальности, как правило, нельзя рассматривать определенную страницу и определенный сайт отдельно от других ресурсов. Тем не менее, моделирование может быть полезно для понимания примерной картины. Неплохой сервис для этого - PageRank Decoder .

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

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

PageRank – это алгоритм ссылочного ранжирования, разработанный для определения относительной важности объекта, связанного с сетью объектов.

Ссылочное ранжирование? Это тип сетевого анализа, определяющий ассоциации (читай, связи) между объектами.

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

Объяснение:

Веб-страницы в интернете связаны друг с другом. Если datascientist..

Но это еще не всё…

Вес балла от сайт оценивается важностью и релевантностью самого сайта.
.

Что означают PageRank равные 0,1,2,3 и так далее? Хотя точное значение числа PageRank компания Google не раскрывает, мы можем получить об этом представление.

И вот как:

Все это выглядит как соревнование по популярности. Мы все имеем представление о том, какие сайты релевантные и популярные. PageRank просто переводит наше представление в цифры.

Как еще применяется PageRank? PageRank был специально разработан для всемирной сети.

Вот 3 инновационных применения PageRank:

Доктор Стефано Аллесина (Stefano Allesina) из Чикагского университета применил PageRank в сфере экологии, чтобы определить, какие из особей являются жизненно важными для поддержания экосистемы.
Twitter разработал WTF (Who-to-Follow) – персонализированный вариант рекомендательного движка, основанного на PageRank, показывающий список людей, на которых стоит подписаться.
Бин Жэнь (Bin Jiang) из Гонконгского политехнического университета использовал вариант PageRank для предсказания перемещения людей на основании топологических метрик в Лондоне.

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

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

Где он используется? Торговая марка PageRank принадлежит компании Google. Однако алгоритм PageRank запатентован Стэндфордским университетом.

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

Вот 3 примера реализации PageRank:

Реализация .
Реализация Python PageRank .
Пакет сетевого анализа igraph в R.

Пример вычисления pagerank (видео)

Алгоритм PageRank на Python

Вот как выглядит алгоритм ранжирования страниц на Питоне (полные инструкции можно найти по ссылке выше):

Python

import operator import math, random, sys, csv from utils import parse, print_results class PageRank: def __init__(self, graph, directed): self.graph = graph self.V = len(self.graph) self.d = 0.85 self.directed = directed self.ranks = dict() def rank(self): for key, node in self.graph.nodes(data=True): if self.directed: self.ranks = 1/float(self.V) else: self.ranks = node.get("rank") for _ in range(10): for key, node in self.graph.nodes(data=True): rank_sum = 0 curr_rank = node.get("rank") if self.directed: neighbors = self.graph.out_edges(key) for n in neighbors: outlinks = len(self.graph.out_edges(n)) if outlinks > 0: rank_sum += (1 / float(outlinks)) * self.ranks[n] else: neighbors = self.graph for n in neighbors: if self.ranks[n] is not None: outlinks = len(self.graph.neighbors(n)) rank_sum += (1 / float(outlinks)) * self.ranks[n] # actual page rank compution self.ranks = ((1 - float(self.d)) * (1/float(self.V))) + self.d*rank_sum return p if __name__ == "__main__": if len(sys.argv) == 1: print "Expected input format: python pageRank.py " else: filename = sys.argv isDirected = False if sys.argv == "directed": isDirected = True graph = parse(filename, isDirected) p = PageRank(graph, isDirected) p.rank() sorted_r = sorted(p.ranks.iteritems(), key=operator.itemgetter(1), reverse=True) for tup in sorted_r: print "{0:30} :{1:10}".format(str(tup), tup) # for node in graph.nodes(): # print node + rank(graph, node) #neighbs = graph.neighbors(node) #print node + " " + str(neighbs) #print random.uniform(0,1) def rank(graph, node): #V nodes = graph.nodes() #|V| nodes_sz = len(nodes) #I neighbs = graph.neighbors(node) #d rand_jmp = random.uniform(0, 1) ranks = ranks.append((1/nodes_sz)) for n in nodes: rank = (1-rand_jmp) * (1/nodes_sz) trank = 0 for nei in neighbs: trank += (1/len(neighbs)) * ranks rank = rank + (d * trank) ranks.append(rank)

import operator

import math , random , sys , csv

from utils import parse , print_results

class PageRank :

def __init__ (self , graph , directed ) :

self . graph = graph

self . V = len (self . graph )

self . d = 0.85

self . directed = directed

self . ranks = dict ()

def rank (self ) :

if self . directed :

self . ranks [ key ] = 1 / float (self . V )

else :

self . ranks [ key ] = node . get ("rank" )

for _ in range (10 ) :

for key , node in self . graph . nodes (data = True ) :

rank_sum = 0

curr_rank = node . get ("rank" )

if self . directed :

neighbors = self . graph . out_edges (key )

for n in neighbors :

outlinks = len (self . graph . out_edges (n [ 1 ] ) )

if outlinks > 0 :

rank_sum += (1 / float (outlinks ) ) * self . ranks [ n [ 1 ] ]

else :

neighbors = self . graph [ key ]

for n in neighbors :

if self . ranks [ n ] is not None :

outlinks = len (self . graph . neighbors (n ) )

rank_sum += (1 / float (outlinks ) ) * self . ranks [ n ]

# actual page rank compution

self . ranks [ key ] = ((1 - float (self . d ) ) * (1 / float (self . V ) ) ) + self . d * rank_sum

return p

if __name__ == "__main__" :

if len (sys . argv ) == 1 :

print "Expected input format: python pageRank.py "

else :

filename = sys . argv [ 1 ]

isDirected = False

if sys . argv [ 2 ] == "directed" :

isDirected = True

graph = parse (filename , isDirected )

p = PageRank (graph , isDirected )

p . rank ()

sorted_r = sorted (p . ranks . iteritems () , key = operator . itemgetter (1 ) , reverse = True )

for tup in sorted_r :

print "{0:30} :{1:10}" . format (str (tup [ 0 ] ) , tup [ 1 ] )

# for node in graph.nodes():

# print node + rank(graph, node)

#neighbs = graph.neighbors(node)

#print node + " " + str(neighbs)

#print random.uniform(0,1)

def rank (graph , node ) :

nodes = graph . nodes ()

#|V|

nodes_sz = len (nodes )

neighbs = graph . neighbors (node )

rand_jmp = random . uniform (0 , 1 )

ranks =

ranks . append ((1 / nodes_sz ) )

for n in nodes :

rank = (1 - rand_jmp ) * (1 / nodes_sz )

trank = 0

for nei in neighbs :

trank += (1 / len (neighbs ) ) * ranks [ len (ranks ) - 1 ]

rank = rank + (d * trank )

ranks . append (rank )

Алгоритм PageRank в R

Вот как выглядит алгоритм ранжирования страниц на R (более подробную инструкцию можно найти по ссылке):

## Download and install the package install.packages("igraph") ## Load package library(igraph) ## Usage page.rank (graph, algo = c("prpack", "arpack", "power"), vids = V(graph), directed = TRUE, damping = 0.85, personalized = NULL, weights = NULL, options = NULL) page.rank.old (graph, vids = V(graph), directed = TRUE, niter = 1000, eps = 0.001, damping = 0.85, old = FALSE)

## Download and install the package

install . packages ("igraph" )

## Load package

library (igraph )

## Usage

page . rank (graph , algo = c ("prpack" , "arpack" , "power" ) ,

= 0.85 , old = FALSE )

Аргументы

graph
The graph object.

algo
Character scalar, which implementation to use to carry out the calculation. The default is «prpack», which uses the PRPACK library (https://github.com/dgleich/prpack). This is a new implementation in igraph version 0.7, and the suggested one, as it is the most stable and the fastest for all but small graphs. «arpack» uses the ARPACK library, the default implementation from igraph version 0.5 until version 0.7. power uses a simple implementation of the power method, this was the default in igraph before version 0.5 and is the same as calling page.rank.old.

vids
The vertices of interest.

directed
Logical, if true directed paths will be considered for directed graphs. It is ignored for undirected graphs.

damping
The damping factor (‘d’ in the original paper).

personalized
Optional vector giving a probability distribution to calculate personalized PageRank. For personalized PageRank, the probability of jumping to a node when abandoning the random walk is not uniform, but it is given by this vector. The vector should contains an entry for each vertex and it will be rescaled to sum up to one.

weights
A numerical vector or NULL. This argument can be used to give edge weights for calculating the weighted PageRank of vertices. If this is NULL and the graph has a weight edge attribute then that is used. If weights is a numerical vector then it used, even if the graph has a weights edge attribute. If this is NA, then no edge weights are used (even if the graph has a weight edge attribute.

options
Either a named list, to override some ARPACK options. See arpack for details; or a named list to override the default options for the power method (if algo=»power»). The default options for the power method are niter=1000 and eps=0.001. This argument is ignored if the PRPACK implementation is used.

niter
The maximum number of iterations to perform.

eps
The algorithm will consider the calculation as complete if the difference of PageRank values between iterations change less than this value for every node.

old
A logical scalar, whether the old style (pre igraph 0.5) normalization to use.

Пример

G3 , personalized = reset ) $ vector

Итак, немного фактов о самом pagerank:

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

Каждая уникальная страница сайта, проиндексированная Google, имеет вес PageRank. Люди часто ошибаются, думая о весе сайта, который на самом деле является весом главной страницы этого сайта.

Внутренние ссылки сайта учитываются при расчете веса PageRank для других страниц сайта.

PageRank независим, он не принимает во внимание текст ссылок и т.д. Конечно, они связаны, но говорить, что это одно и то же, это все равно что говорить, будто тэг Title то же самое, что ключевые слова в тексте.

Дополнительные файлы: и презентация с примерами (англ.).

Чтобы вычислить PageRank для страницы, необходимо учесть все внутренние и внешние ссылки на эту страницу. Ниже приведено уравнение для расчета значения PageRank страницы А.

PR(A)=(1-d) + d(PR(t1)/C(t1) + … + PR(tn)/C(tn))

PR(t1…tn) - вес страницы, ссылающейся на страницу A

C - количество исходящих ссылок со страницы А

d - коэффициент затухания, обычно принимаемый 0.85.

Страница «голосует» своим значением PageRank на каждую страницу, на которую она ссылается. Голосующее значение для страницы складывается из собственной величины PageRank этой страницы * 0.85. Эта величина распределяется равномерно между всеми страницами, на которые ведут исходящие ссылки.

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

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

Уравнение ясно показывает, откуда берется значение PageRank для любой страницы. Предположим, что у нас есть 2 страницы, A и B, какая ссылается друг на друга, никаких других ссылок на этих страницах нет. Вот что случается:

Вычисление Google PageRank для страницы А

Шаг 1 : Вычислим значение PageRank для страницы A

Страница теперь имеет новое значение PageRank. Для вычисления использован вес исходящей ссылки со страницы B. Но страница B также имеет исходящую ссылку на страницу A и полученное значение PageRank не может быть точным, пока не известно значение PageRank для страницы В.

Вычисление Google PageRank для страницы B

Шаг 2 : Вычислим значение PageRank для страницы B

Страница B теперь имеет новое значение PageRank, которое не может быть точным, поскольку для вычисления использовано неточное значение PageRank со страницы A.

Мы не можем вычислить точное значение PageRank для страницы A, пока мы не узнаем значение PageRank для страницы B, и мы не можем вычислить точное значение PageRank для страницы B, пока не узнаем значение PageRank для страницы A.

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

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

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

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

Как лучше управлять индексацией внутренних ссылок на сайте, чтобы повысить PR его отдельных страниц? Рассмотрим формулу, по которой вычисляется PR для текущей страницы A:

здесь d – коэффициент затухания ссылочного веса, точное его значение скрывается Гуглом, обычно его принимают за 0,85. В контексте нашего вопроса это несущественно, так как мы хотим оценить PR выбранных страниц на сайте относительно всех остальных;
T 1 ,…, T n – страницы, ссылающиеся на А ;
PR(T 1 ) ,…, PR(T n ) – PR ссылающихся страниц;
С(T 1 ) ,…, С(T n ) – количество ссылок на ссылающихся страницах.

Особенности:

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

Как же пользоваться этой формулой, ведь в правой части указаны PR страниц, которые тоже предстоит вычислить? Возьмем все-все страницы в Интернете, проиндексированные Гуглом и примем начальный PR каждой из них за единицу, затем последовательно вычислим Page Rank для всех. Это была первая итерация, в результате которой каждая страница получила какое-то значение PR. Повторяем много раз вычисления по этому алгоритму, используя в качестве PR страниц величины, полученные на предыдущем шаге. Особенность алгоритма состоит в том, что какой бы начальный PR мы не взяли и в каком бы порядке не вычисляли его, за достаточно большое количество итераций мы придем к одним и тем же числам.

Однако, привычный всем целочисленный PR от 0 до 10 – это не то, что мы получили в предыдущем абзаце. PR 0…10 – так называемый "Тулбарный" PR (ToolBar PageRank ), он введен для того, чтобы можно было представить все значения PR в абсолютных величинах независимо от количества страниц в сети. Вот он:

где base – некое число, зависящее от количества страниц в индексе Гугла и других факторов, обычно берут base равное 7;
a – коэффициент приведения, 0 < a ≤ 1, чаще всего принимают за 1.

Коэффициенты base и a , как и сама формула для TLPR нам сейчас не важны, главное, что увеличение TLPR всегда связано с увеличением PR, поэтому сконцентрируемся на последнем. Забудем про внешние ссылки на другие ресурсы и попробуем рассчитать PR исходя только из внутренних факторов. Допустим, у нас есть сайт, состоящий из шести страниц:

На каждой есть меню: "Главная страница", "О сайте", "Список статей". На пункты меню ссылаются все страницы сайта. "Список статей" кроме этого ссылается еще на страницы со статьями. Page Rank при таком ссылочном распределении обозначен на схеме сверху. При расчете PR я сделал 100 итераций, взяв за начальное значение единицу и округлил полученные числа до сотых после запятой.

Допустим, мы хотим продвигать только главную страницу. Чтобы повысить ее PR, логично будет разрешить индексировать лишь те ссылки, которые на нее ведут. Учтем при этом, что ни одна страница не должна оказаться отсеченной от сайта, то есть на каждую должна быть поставлена индексируемая ссылка:

Что ж, PR требуемой страницы возрос. Попробуем теперь поставить с нее ссылку на "Статью 1" и посмотрим, как изменится распределение:

Казалось бы, ставя лишнюю ссылку на главной странице, мы должны уводить с нее ссылочные вес и тем самым ослаблять ее. Но на деле оказывается совсем наоборот – ссылочный вес возвращается с прибавкой! Этим действием мы одновременно поднимает и "Статью 1".

Пусть теперь мы передумали и решили раскручивать только список статей:

Только что нам удалось получить больший PR из всех вычисленных ранее, равный 2,8 для списка статей. Как показывает данный пример, проще увеличить PR страницы, имеющей много внутренних ссылок, при условии конечно, что на нее будут установлены обратные. Этот же эффект был продемонстрирован, когда мы делали ссылку на "Статью 1" с главной.

А теперь нарушим логическую структуру сайта: поставим с главной страницы ссылки на все остальные, а со всех страниц на главную. Другие же ссылки закроем от индексации.

Лучше всего удается увеличить Page Rank страниц со множеством ссылок, при условии установки обратных. К таким страницам относятся форумы, списки статей, карты сайтов и т.д
PR страницы здорово поднимается, если поставить на нее ссылку со страниц из п.1, аккумулирующих Page Rank.
Для увеличения PR главной страницы на нее будет полезно помещать анонсы статей, новостей и т.д., ведущие на страницы с полным текстом. Опять же, не забываем про обратные ссылки.

А вот и скрипт, который поможет вам с расчетом PR. Поэкспериментируйте с разными вариантами индексации ссылок на сайте.

// массив страниц сайта: первый элемент в массиве каждой страницы - ее название,

// все остальные элементы - индексы страниц в массиве, на которые есть ссылка с текущей

$pages = array

array ("Главная страница" , 1 , 2 ) ,

array ("О сайте" , 0 , 2 ) ,

array ("Список статей" , 0 , 1 , 3 , 4 , 5 ) ,

array ("Статья 1" , 0 , 1 , 2 ) ,

array ("Статья 2" , 0 , 1 , 2 ) ,

array ("Статья 3" , 0 , 1 , 2 )

// устанавливаем страницам начальное значение PR = 1

for ($i = 0 ; $i < count ($pages ) ; $i ++ ) $pr [ $i ] = 1 ;

// количество итераций = 100

for ($i = 0 ; $i < 100 ; $i ++ )

for ($j = 0 ; $j < count ($pages ) ; $j ++ )

$add = 0 ; // прирост от внешних ссылок

for ($k = 0 ; $k < count ($pages ) ; $k ++ )

if ($k == $j ) continue ;