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

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

Крисом Райдингсом (Chris Ridings) и Джиллом Вэйленом (Jill Whalen) в работе [1] дается следующее определение: PageRank — это метод Google для измерения «важности» страницы. Когда все другие факторы, такие как тэг Title и ключевые слова учтены, Google использует PageRank, чтобы откорректировать результаты так, что более «важные» сайты поднимутся соответственно вверх на странице результатов поиска пользователя.

Согласно Филу Крэйвену PageRank Google — это его собственный способ определения важности оцениваемой страницы. PageRank представляет собой численное значение, которое отражает, насколько значима данная страница в Интернете [2]. Google полагает, что когда одна страница ссылается на другую, она словно «отдает свой голос» за другую страницу. Тогда, чем больше голосов отдано за страницу, тем важнее эта страница должна быть. Кроме того, «отданные голоса» отличаются по значимости в зависимости от того, «кто» голосует. Google подсчитывает важность оцениваемой страницы, исходя из «голосов», отданных за нее. При этом в процессе производства расчетов Google учитывает, насколько важен (весом) каждый из отданных «голосов».

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

За основу PageRank был выбран академический подход оценки важности публикации автора по числу её упоминаний в библиографических ссылках других авторов. Для адаптации к применению в Интернет в алгоритм были внесены следующие изменения: вес каждой ссылки учитывается индивидуально и нормируется по числу ссылок на ссылающейся странице. Кроме того, PageRank может быть интерпретирован в терминах случайного блуждания [3].

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

      

 

 

 






(1)
 

 

 

 

 

 

 

 

При этом, что важно, во всех статьях указывается, что сам алгоритм вычисления PageRank итерационный (следовательно, не линеен по своей сути). Примечательно, что именно здесь вводится так называемый “коэффициент затухания”. По сути своей этот коэффициент есть вероятность  того, что пользователь последует по ссылке (хотя бы одной из всей совокупности ссылок) на текущей странице. Следовательно, (1-d) – вероятность т.н. “случайного прыжка ” – ухода пользователя с текущей страницы не по ссылке на текущей странице, а каким либо другим образом.

 А. Шкодин приводит модель расчета PageRank, которая основана на оценке  вероятности посещения страницы среднестатистическим пользователем [3]. Любопытно, что вероятность  того, что пользователь последует по ссылке на текущей странице (аналог коэффициэнта затухания d в предидущей модели) в согласно данной статьи находится в пределах 0.85 < d < 0.9 .

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

Такая модель полностью соответствует утверждению, высказанному в работе [1], о том, что PageRank — это, по сути, вес страницы.

По данным выступлений основателей Google, миллиарды страниц интернета имеют средний вес PageRank порядка 1.0 на страницу. Таким образом, общий PageRank интернета эквивалентен количеству страниц на вебе, умноженному на 1, что в масштабах всего интернета дает огромное количество PageRank, распределяемого внутри всего Интернета  [2].

Согласно результатам исследований [4] сейчас Google индексирует порядка 3 миллиардов страниц. И количество страниц утраивается каждый год. Следовательно, логично предположить, что суммарный PageRank – величина такого же порядка.

Пользователю доступна некая оценка истинного значения PageRank, отображаемая в ToolBar Google. Далее в статье она будет обозначаться как PR. (В статье [1] предлагается ввести понятия “Настоящий PR” для обозначения подлинного веса PageRank, хранимого Google, и “Тулбаровский PR”  для обозначения довольно скупого представления того, что тулбар Google позволяет нам видеть).

ToolBar Google дает только представление реального веса PageRank.  В то время как вес PageRank линеен, Google решили показывать его на нелинейной диаграмме. Шкала на ToolBar Google градуирована от 1 до 10 [2].

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

Т.е. отображаемое значение целочисленное PR связано с весом PageRank соотношением, близким к:

PR=[Log _x (PageRank)]       (2)

Где [] – операция выделения целой части числа.

По поводу  значения основания логарифма X нет единого мнения. Фил  Крэйвен на момент написания статьи полагал, что на самом деле, навряд ли основание логарифма составляет ровно 10. Некоторые исследователи считали, что это 5 или 6, а, возможно, даже и менее [2].

Но, с другой стороны:

- во первых, согласно выступлению основателей Google “ общий ПэйджРанк интернета эквивалентен количеству страниц, о которых поисковику известно,  умноженному на 1” [2];

- во вторых, согласно работе [3], функция распределения плотности вероятности посещения страницы среднестатистическим пользователем распределена по всему количеству страниц, известных поисковой системе, с весом, равным PageRank. Т.е. согласно этой модели, вероятность посещения хотя бы одной страницы из всех индексируемых поисковиком равна 1;

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

Собственно говоря, последнее, вероятнее всего, и происходит.  По мере того как количество страниц в Интернет постоянно возрастает, суммарный PageRank также растет. А, коль скоро растет суммарный PageRank, расположение позиций градуировки шкалы должно меняться. При этом некоторые страницы опускаются на указателе ToolBar по «непонятным» причинам. Это является еще одним косвенным свидетельством пересчета и коррекции значения основания логарифма x.

Согласно результатам исследований [4] на момент написания этой статьи  Google индексирует порядка 3 миллиардов страниц. И количество страниц утраивается каждый год. Следовательно, логично предположить, что суммарный PageRank – величина такого же порядка.

Из всего вышесказанного вполне логичным представляется вывод, что значение x  может быть найдено из уравнения (2) при подстановке в него значений PR=10, PageRank=3*10E9.  Получаем x~9.5.

Можно, конечно, положить определенное количество денег и времени на уточнение значения основания логарифма x. Но имеет ли это какой – либо смысл? Тем более, что с большой вероятностью можно утверждать то, что он растет с повышением общего количества страниц в сети. И уж точно, если не сегодня, то завтра превысит значение x=10.

Как бы там ни было, сути предлагаемого далее подхода к оценке эффективности получаемой ссылки, значение x не меняет.

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

Допустим, имеется некая страница, назовем ее A, c показателем по шкале ToolBar = PR_A.  Вероятность посещения этой страницы  p_а среднестатистическим пользователем равна отношению PageRank_А / PageRank_Общ .

p_а = x ^(PRa-10)

Допустим, имеется некая страница, назовем ее B, c показателем по шкале ToolBar = PR_B.  Вероятность посещения этой страницы  pb среднестатистическим пользователем равна отношению PageRank_B / PageRank_Общ .

p_b = x ^(PRb-10)

Пусть страница B имеет общее количество ссылок Nb . Именно общее, по скольку при расчёте PageRank никто не обещал  разделять ссылки на внешние и внутренние. (Распространено заблуждение, что на качество ссылки влияет именно количество внешних ссылок. При этом забывают о том, что часть отдаваемого  PageRank перераспределяется  и на внутренние ссылки так же).
Пусть страница B  ссылается на страницу А. Тогда вероятность перехода со страницы B на А,  согласно  известным моделям,  вычисляется  как  вероятность перехода по одной из общего количества ссылок при условии  попадания  на ресурс B:

p_ba = d*( x ^(PRb-10) )/ Nb

В результате получаемая вероятность попадания  пользователя на ресурс А повышается до значения:

p_{а суь}= 1 – ( 1 - pа)( 1 - pba )

Для малых значений  p_а  и  pb_a  с  абсолютной погрешностью порядка  порядка  p_а  * p_ba   справедливо приближенное  выражение:

p_а сум~  p_а + p_ba

В общем случае,  для некоторого количества  ссылающихся страниц  K, полученная вероятность  посещения страницы А  может быть вычислена как:




Если следовать предложенной модели, то зная «собранную» суммарную вероятность посещения ресурса  p_{а сум} , можно вычислить ожидаемое значение показателя  ToolBar:

PR _{а сум} = Log _x ( X ¹⁰ * p_{а сум}  )

Здесь, однако, следует сделать 2 замечания.

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

               
Численные примеры:
 
Допустим, (в недалеком будущем) основание логарифма  ToolBar  x = 10 .  Допустим, мы располагаем  страницей с PR_A = 3 , на которую ссылается страница с  PR_B = 5 при общем количестве ссылок, равном  N_b = 40 .  Ситуация вполне  реальная.  Получаем следующие значения вероятностей посещений страниц:

p_а = x ^(PRa-10) = 10^-7 ;  p_b = x ^(PRa-10) = 10^-5 ;  p^ba = d*( x ^(PRb-10) )/ N_b = 2.125* 10^-7 ;

p_{а сум}~  3.125 * 10^-7 ;  PR а _сум  = 3.   Т.е. такая ссылка повысит (существенно)  вероятность посещения страницы А, примерно в 3 раза.  Но к повышению PR при следующем пересчете, вероятнее всего не приведет.  Имеет ли смысл такая ссылка?  Очевидно – да.  По той  очевидной причине существенного повышения вероятности посещения страницы.

Допустим,  ссылающаяся страница  B имеет PR_B = 6 при общем количестве ссылок, равном  N_b = 85 :

p_а = x ^(PRa-10) = 10^-7 ;  p_b = x ^(PRa-10) = 10^-4 ;  p_ba = d*( x ^(PRb-10) )/ N_b = 1.0 * 10^-5 ;

p_{а сум}~  1.01 * 10 ^-5 ;  PR _{а сум}  = 5.  Примечательно, что в этом случае получаемый в результат практически не зависит от начального значения  PRA ,  Однако, учитывая  оговоренные поправки на точность модели, можно утверждать, что в этом случае страница А получает ToolBar PR_A = 4 гарантированно.

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

В настоящее время появляется целый ряд работ,  позволяющих существенно сократить вычислительные  затраты  поисковых систем.  Так, один из участников  так называемого стенфордского проекта Сепандар Камвар говорит следующее:  «При использовании всех этих методов возможно еще большее ускорение, Наши предварительные эксперименты показывают, что их комбинация сделает вычисление PageRank впятеро быстрее. Однако нам предстоит решить ряд проблем. Сейчас мы ближе к тематическому PageRank, чем к персонализированному ранжированию» [4].   Здесь хочу отметить, что когда будет введена такая величина, как “тематический PageRank”, и, если (!) шкала, его отображающая будет использовать алгоритмы, аналогичные  ToolBar Google, то значения основания логарифма x для должно быть значительно ниже 10-ки. В этой связи рекомендации, высказанные в свое время Бобом Масса (Bob Massa) [5] приобретают особый смысл:

“Если вы хотите добиться лучших рейтингов в результатах поиска, вне зависимости от того, проводит ли индексацию робот-паук или человек, вам просто надо «думать» как человек, а не как компьютерная программа. Логика, здравый смысл и вежливость по отношению к другому человеку всегда будут лучше, чем любой компьютерный язык. Если вы поймете, что вы работаете с реальными людьми, которые не так уж и сильно отличаются от вас самих, перестанете думать, что вы – всего лишь имя пользователя и пароль, пытающиеся обмануть компьютер, то уровень трафика (и, что намного важнее, уровень продаж) возрастет”.


Список литературы

[1] Растолкованный PageRank,

http://portal.adverman.com/modules/news/article.php?storyid=306

http://www.digits.ru/articles/promotion/pagerank.html

Написано и придумано Крисом Райдингсом (Chris Ridings). Отредактировано Джилл Вэйлен (Jill Whalen). Переведено на русский язык и прокомментировано Александром Садовским.

[2] Что такое PageRank (ПэйджРанк) Google'а и как его получить

http://portal.adverman.com/modules/news/article.php?storyid=311

http://www.bdbd.ru/articles/what_is_googles_pagerank_part_one.htm

Фил Крэйвен

[3] PageRank: Больше ссылок хороших и важных
http://www.developing.ru/seo/pagerank.html    

А. Шкондин

[4] Google может считать PageRank впятеро быстрее

http://promo.by/searchengines/google_up.html

[5] Основные правила web-оптимизации

http://portal.adverman.com/modules/news/article.php?storyid=338

Автор: Боб Масса (Bob Massa)



Написано специально для AdverMAN.com.

Статья занесена в каталог статей “NEXT”


М.В.Михайленко, к.т.н.

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

Дело в том, что ToolBar Google выводится значение нижней границы диапазона изменений PageRank. Т.е., допустим, если значение, выдаваемое ToolBar = 3, то это значит, что реальное значение будет находится где-то в пределах от 3 до 4. Точно такая же ситуация и для сайтов с PageRank = 10. Их реальное значение может быть несколько выше, чем то, которое соответствует в точности 10-ти.

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

С точки зрения математической модели эти изменения эквивалентны введению в ToolBar нового значения, равного 11. Интересно отметить, что в англоязычных форумах по данной тематике иногда встречаются предположение о том, что есть, якобы, сайты с PageRank «до 11».  На самом деле, следует понимать, что ToolBar Google выводится значение нижней границы диапазона изменений PageRank. В этом случае значение «11» является верхней границей, которая никогда не может быть достижима.  ToolBar PageRank не может быть равен 11 для какой-либо из страниц, по той причине, что вероятность посещения любой, из всех имеющихся в Интернет, страницы не может быть равна 1.  Т.е. существует некое распределение плотности вероятности посещения по всем страницам (отображаемое реальным значением PageRank), находящимся в базе данных поисковой системы.  Эта ситуация напоминает детскую задачу о необходимом количестве распилов карандаша, деленного на N частей.

В алгоритме, реализованном на сайте pr.master.in.ua , все указанные изменения учтены. 

Хочу выразить признательность CryAngel, реализовавшему инструменты "Мастера" -  lr.seo-master.net ,   pr.master.in.ua  и  "SERP Tool".

13.02.06,  Максим Михайленко.   

Появилось сообщение об особенностях алгоритма обработки информации для случая обнаружения обмена ссылками. Если установлено, что на сайтах ссылки взаимны, то для такой ссылки в формулу (1) подставляется "коэффициент затухания" d, меньший, чем "стандартный" используемый. Конкретные значения понижения d не разглашаются.  Следовательно, с точки зрения алгоритма, в случае линкообмена измениться (снизиться) и ссылочная ценность таких страниц LinkRank. 

18.03.06,  Максим Михайленко.  

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

12.04.06,  Максим Михайленко.