Расчет pagerank. Как вычисляется Google PageRank - реальная формула

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

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

В этой статье мы излагаем только факты.

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

Наиболее важные факты кратко описаны в начале статьи.

Как работает PageRank?

1. PageRank один из многочисленных методов используемых Google для определения релевантности и важности страницы.
2. Google интерпретирует ссылку со страницы A на страницу B как голос A в пользу B, конечно учитывается не только количество голосов, но и качество голосующих страниц.
3. PageRank основан на количестве входящих ссылок , но не только на нем, релевантность и качество тоже важны.
4. Не все ссылки одинаково влияют на PageRank.
5. Если на странице с PR8 есть только одна ссылка, то сайт, на который она ссылается, получит весь PR который она может передать, если же ссылок 100 то каждая ссылка будет передавать только часть этого PR.
6. Плохие входящие ссылки не влияют на PR.
7. В PR учитывается время существования сайта, релевантность входящих ссылок и время их существования.
8. При расчете PR контент не учитывается.
9. PR рассчитывается не для сайта в целом, а для каждой страницы в отдельности.
10. Важна каждая входящая ссылка, за исключением ссылок с забаненых сайтов.
11. PR это не только целые значения от 0 до 10, это вещественное число.
12. Достичь каждого следующего уровня PR все сложнее, предположительно используется логарифмическая шкала.
13. PR пересчитывается постоянно, но данные для тулбара обновляются раз в несколько месяцев.
14. Google старается найти страницы солидные и релевантные одновременно.

Факторы, влияющие на PageRank

1. Частые обновления сайта не увеличивают PR автоматически.
2. Высокий PR не гарантирует высокие позиции в результатах поиска.
3. Каталоги DMOZ и Yahoo! не увеличивают PR автоматически.
4. .edu и.gov сайты не увеличивают PR автоматически.
5. Внутренние страницы не обязательно имеют меньший PR чем главная.
6. Ссылки с сайта Wikipedia не увеличивают PR автоматически.
7. Ссылки с атрибутом nofollow не влияют на PR.
8. Эффективные внутренние ссылки влияют на PR.
9. Ссылки с тематических сайтов влияют сильнее.
10. Текст, используемый в ссылке, часто может быть важнее, чем PR ссылающейся страницы.
11. Исходящие и входящие ссылки на качественные тематические сайты положительно влияют на PR.
12. Несколько одинаковых ссылок с одной страницы считаются за одну.
13. Сайт может быть забанен за ссылки на забаненные сайты.

1.1 Что такое PageRank?

• PR это только один из методов используемых Google для определения релевантности и важности страницы. [PageRank Explained Correctly 6 ]
• Google использует множество факторов для ранжирования страниц, PageRank один из лучших . PR отражает два важных момента, как много страниц ссылаются на данную и какого уровня страницы на нее ссылаются. Пять шесть ссылок с таких сайтов как www.cnn.com 7 или www.nytimes.com 8 , могут быть более полезны, чем гораздо большее количество ссылок с менее солидных сайтов. [Google Librarian Central 9 ]
• PR может отражать только приблизительное качество страницы , но никак не связан с ее тематической релевантностью, которую можно определить только учитывая контекст ссылок, и такие факторы как плотность ключевых слов, заголовок страницы и т.п. [PageRank: An Essay 10 ]

1.2 Как работает PageRank?

• Никто точно не знает, как Google рассчитывает PR. [Google PageRank Explained 11 ]
• PR(A) = (1-d) + d(PR(t1)/C(t1) + … + PR(tn)/C(tn)). Так выглядит примерная формула расчета PR, где t1-tn страницы, ссылающиеся на A, С(tn) количество исходящих ссылок на соответствующий странице, d коэффициент обычно равный 0.85.
• Можно предположить, что PR вычисляется по формуле PR = 0.15 + 0.85 * (часть PR каждой ссылающейся страницы передаваемая нашей). Количество PR, которое страница может использовать, чтобы голосовать за другие, чуть меньше чем ее собственный PR, а точнее 0.85 * PR, это количество и делиться между страницами, на которые она ссылается. [Google’s Page Rank 12 ]
• Алгоритм вычисления PR, основан на распределении собственного PR страницы, между страницами на которые она ссылается. К примеру, если на странице с PR8 есть только одна ссылка, то страница, на которую она ссылается, получит весь доступный PR, но если на этой странице 100 ссылок, то каждая из них получит только сотую часть доступного PR. [The Importance of PageRank 13 ]
• Вследствие, такого алгоритма вычисления PR, ссылка со страницы с PR4 и 5 внешними ссылками, эффективнее ссылки со страницы с PR8 и 100 внешних ссылок. PR ссылающихся страниц важен, но не менее важно и количество исходящих ссылок, которое они содержат, чем больше исходящих ссылок тем меньше PR перейдет каждой. [Google’s Page Rank 12 ]
• PR использует входящие ссылки как индикатор важности страницы. Google интерпретирует ссылку со страницы A на страницу B как голос страницы A в пользу страницы B. Учитывается не только количество голосов, но и качество голосующих страниц. Чем выше PR страницы, тем большее значение имеет ее голос. [Google: Technology 14 ]
• Не все ссылки одинаково полезны. Чем выше PR ссылающейся страницы, тем больший PR она передает, но нужно учитывать и то, что этот PR делиться в равной степени между всеми страницами на которые она ссылается. Поэтому ссылка со страницы с PR4 и единственной исходящей ссылкой, может дать больше чем ссылка со страницы с PR5 и 100 исходящих ссылок. Типичный пример всем известные миллионодоларовые главные страницы, такая страница с PR7 и сотнями исходящих ссылок, несмотря на свою важность, передает другим страницам незначительный PR. [Google PageRank Explained 11 ]
• Каждый следующий уровень PR достигается значительно сложнее предыдущего. При вычислении PR используется логарифмическая шкала, это значит, что для перехода с PR0 к PR1 требуется один шаг, несколько труднее набрать PR3, еще труднее PR4, и значительно труднее PR5. [Google Page Rank FAQ 15 ]
• PR вычисляется не для сайта в целом, а для каждой отдельной страницы и рекурсивно связан с PR страниц которые на нее ссылаются. [The Page Rank algorithm 17 ]
• Google комбинирует PR со сложными техниками текстового поиска , анализируются многие аспекты содержимого страницы и ссылающихся на нее страниц, чтобы найти страницы лучше других, соответствующие запросу пользователя. [What Is Google PageRank? 18 ]
• PR пересчитывается постоянно, но данные для тулбара обновляются раз в несколько месяцев , новым сайтам присваивается PR0. [Google PageRank Explained 11 ]
• PR это не только целые значения от 0 до 10, PR вещественное число. Правильно думать о PR как о вещественном числе, потому что при внутренних вычислениях мы используем множество градаций, а не только значения от 0 до 10 отображаемые в тулбаре. [Matt Cutts 19 ]
• Робот не анализирует сайты мгновенно. Часто необходимо два полных апдейта чтобы все входящие ссылки были обнаружены, засчитаны и отображены как входящие ссылки. [Google FAQ 20 ]

1.3 Факторы, влияющие на PageRank

• Важна каждая входящая ссылка, за исключение ссылок с забаненных сайтов. PR это своеобразная система голосования, каждая ссылка на страницу это голос в ее пользу. Страницы с высоким PR считаются более важными, и их голоса в некоторых случаях имеют большее значение, но в основном, чем больше входящих ссылок, тем лучше. [Google PageRank FAQ 21 ]
• Добавление новых страниц может уменьшить PR. Этот эффект заключается в том, что суммарный PR сайта возрастает, но одна или нескольких старых страниц теряют часть PR, за счет чего новые его получают, чем больше добавлено страниц тем больше PR теряют существующие. На крупных сайтах этот эффект незаметен, но на малых его иногда можно наблюдать. [PageRank Explained 12 ]
• Уменьшение PR. PR страницы может уменьшиться из-за исчезновения некоторых важных ссылок, которые передавали ей PR, или падения PR ссылающихся на нее страниц. [Google PageRank FAQ 22 ]
• Заголовки (h1, … , h6) и теги strong важны, но не влияют на PR. Используйте мета-теги, заголовки и теги b, strong, но так чтобы контент оставался читабельным и полезным. Обращайте внимание на текст окружающий ключевые слова, поисковики все лучше работают с семантикой, поэтому контекст ключевых слов очень важен.
• Большое значение имеет эффективность внутренней структуры сайта. Страницы на сайте должны быть связаны как можно более простым способом, в идеале не должно быть страниц в более чем трех кликах от главной. [ 23 ]
• Ссылки с и на тематические сайты с высоким PR очень важны. Чем ближе тематика страниц, тем больше PR передает ссылка. Ссылки на уважаемые сайты с близкой тематикой показывают поисковым машинам, что сайт полезен для посетителей, это не всегда верно для сайтов, которые существуют уже несколько лет и имеют высокий рейтинг в Google. Ссылаясь только на качественные сайты, можно получить некоторое преимущество перед конкурентами. [Let Google’s Algorithm Show You The Traffic 23 , FAQ 15 ]
• Важен текст ссылки. Чем более специфичен текст ссылки тем лучше Google может связать ее с запросами пользователей.
• Ссылочные фермы (линкопомойки) пенализируются. Google заинтересован в страницах содержащий менее 100 исходящих ссылок, страницы с большим количеством ссылок считаются ссылочными фермами и пенализируются. [Google FAQ 24 ]
• Очень важны входящие ссылки с популярных сайтов. Если на страницу ссылаются страницы с высоким PR она получает часть их репутации.
• Сайт может быть забанен, если ссылается на забаненные сайты. Будьте очень осторожны с исходящими ссылками, не ссылайтесь на подозрительные сайты (линкопомойки, забаненные сайты и т.д.), Google может пенализировать ваш сайт за такие ссылки, всегда проверяйте PR сайтов на которые ссылаетесь. [SiteProNews 25 ]
• Мошенничество наказывается пенализацией PR и может привести к бану. Скрытый текст, редиректы, клоакинг, автоматизированный обмен ссылками и другие действия, противоречащие Google’s quality guidelines 26 , могут привести к бану сайта в Google.
• Google учитывает время существования сайта, релевантность входящих ссылок, и время их существования , если входящая ссылка не релевантна она не будет давать много PR.
• Миф: чем выше PR тем выше позиция в результатах поиска. Конечно, страницы с высоким PR в результатах поиска расположены выше, чем конкуренты с меньшим PR, но нельзя забывать, что Google учитывает контекст входящих ссылок, и только те ссылки, которые связаны со словами в запросе позволяют занять высокое место в результатах поиска по этому запросу. [

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

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

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

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

Что такое PageRank и зачем он нужен?

Слово PageRank буквально можно перевести как "ранг страницы". Само название определяет алгоритм расчета цитируемости, разработанный и используемый by Sergey Brin & Larry Page, разработчиками поисковой системы Google. Русские аналоги - Взвешенный Индекс Цитирования (ВИЦ у Яндекса), есть аналог и у Апорта, Рамблер планирует ввести учет цитируемости осенью 2002 года. В дальнейшем будем употреблять обозначения цитируемость и PR наравне с PageRank.

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

В чем основная идея? Нужно найти жизненный критерий, выражающий важность страницы. В качестве такого критерия была выбрана теоретическая посещаемость страницы. Была построена модель путешествия пользователя по сети путем перехода по ссылкам. При этом есть вероятность того, что посетителю сайт надоест и он закроет броузер и начнет со случайной страницы (допустим, вероятность этого равна 0.15 на каждом шаге). Соответственно, с вероятностью 0.85 он продолжит путешествие, кликнув на одну из доступных на странице ссылок (все ссылки при этом равноправны). Продолжая путешествие до бесконечности, он побывает на цитируемых страницах много раз, а на нецитируемых - меньше. Таким образом, PageRank веб-страницы был определен как вероятность нахождения пользователя на этой веб-странице ; при этом, конечно, сумма вероятностей по всем веб-страницам сети равна единице - где-то он должен обязательно быть!

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

Во-вторых , PR передается не полностью, есть "затухание". Поэтому длинные цепочки ссылок на сайте малополезны. С человеческой точки зрения то же самое выражает известное правило "трех кликов".

В-третьих , каждая страница изначально имеет ненулевой PR, но очень маленький.

Относитесь с осторожностью к расчетам PageRank, если-

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

Аналогия

Представьте себе озеро (сайт), в которое впадают ручьи и речки (потоки посетителей, пусть "теоретических"). Количество потоков может быть любым, но река приносит много воды, а ручей мало. Поэтому в свое озеро нужно направлять мощные потоки. Какая-то часть воды "уходит в песок", остальное вытекает из вашего озера и впадает в другие озёра. Часть воды испаряется.

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

Замечания

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

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

Расчет PageRank

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

PageRank (P i ) страницы i выражается как
{1}

где:
d -т.н. "damping factor", параметр затухания. Принимается равным 0.85-0.9. Выражает вероятность того, что пользователь, зашедший на страницу, будет продолжать путешествие и переходить по ссылкам.
P i - PageRank интересующей нас страницы i
j - обозначение страниц, на которых есть ссылки на i -ю
P j - PageRank страницы j , ссылающейся на i -ю.
С j - Число ссылок на странице j .
1/С j - Вероятность того, что пользователь, находящийся на странице j , из j доступных ему ссылок выберет именно ссылку на нашу страницу i .
d*P j /С j - поток "теоретической посещаемости", который дойдет до страницы i со страницы j . Суммирование идет по всем страницам, ссылающимся на i -ю.
(1-d) - минимальный PageRank страницы. Он не равен нулю за счет того, что пользователь регулярно выбирает новый сайт в качестве стартовой точки.

Однако, на PageRank наложено ограничение:

где N - общее количество веб-страниц в Интернет.

Т.е., средний PageRank равен единице . Ограничение это следует из нормировки вероятности пребывания пользователя по всей сети - сумма вероятностей по всем страницам равна единице. Таким образом,
Вероятность i =PageRank i /число страниц в сети

Отметим, что значение PageRank, равное единице, только кажется большим. Количество страниц в сети (N) очень велико, и вероятность 1/N - чрезвычайно мала.

Решая систему уравнений, можно найти PageRank всех страниц в Интернет. Расчет можно вести разными методами:

Итерационный метод расчета PageRank

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

1. Выбираем геометрию сайта, расстановку ссылок, систему уравнений
2. Задаемся начальными значениями PageRank для каждой страницы. Они могут быть любыми.
3. Рассчитываем новый набор значений PageRank по уравнению (1) исходя из имеющегося набора значений
4. Рассчитываем средний PageRank по всему набору страниц, и делим PR каждой страницы на полученную величину. В результате средний PR становится равным единице.
5. Если набор значений PageRank изменился по сравнению с исходным набором шага 3, возвращаемся к шагу 3. Если нет, то расчет заканчиваем.

При исследовании влияния геометрии сайта на распределение PageRank удобно представить структуру ссылок в виде матрицы:

В таблице выше представлен сайт из четырех страниц, на котором ссылки замкнуты в "кольцо". Страница 1 ссылается на 2 (1- есть ссылка, 0-ссылки нет), 2 на 3, 3 на 4, 4 обратно на 1. Представление структуры сайта в таком виде удобно, в частности для расчетов.

Для того, чтобы поэкспериментировать с различными структурами сайтов, можно скачать заготовки в MS Excel для 10 страниц (30 итераций) и 30 страниц (90 итераций). Распределение PageRank по страницам рассчитывается сразу и представлено в желтой строке.

Матричный метод расчета PageRank

По уравнению 1:

Нижеприведенную "матрицу связей" можно умножить на вектор значений PageRank m -го шага итерации, полученный вектор умножить на d , прибавить единичный вектор, умноженный на (1-d) и получить следующее приближение вектора PageRank с номером m+1 , который нужно пронормировать (чтобы сумма проекций вектора PR была равна N). При навыках работы с математическими программами (например, Mathcad) этот способ может быть более удобным.

	1	2	3	4
1	0	1/3	1/3	1/3
2	0	0	1/2	1/2
3	0	0	0	1
4	1	0	0	0

Здесь страница 1 ссылается на 2, 3, 4; страница 2 - на 3 и 4; страница 3 на 4, а 4 на 1. Представленная матрица содержит значения M ij =1/C j->i , т.е. значение в каждой ячейке разделено на общее количество ссылок C j на странице j .

Недостатки численных и итерационных методов

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

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

Из этого рассуждения следует, что:

• Расчеты PR "в отрыве" от окружения сайта неточны для каждой страницы вашего сайта - они проделаны для нулевого входящего PageRank
• Правило нормировки не работает в пределах вашего сайта (но работает в пределах глобального набора проиндексированных страниц , т.е. в рамках Интернет по версии Google)
• Никакой численный расчет не может применяться в динамике - ведь входящий PageRank изменяется по мере раскрутки сайта (если вы дочитали до этого места, вероятно, раскруткой своего сайта будете заниматься так же упорно). Соответственно, меняется во времени PR каждой страницы.

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

Посмотрим, что происходит при увеличении входящего PageRank.

Вот простейший сайт из четырех страниц, ссылок извне нет-

А здесь входящий PageRank равен единице-

Но нам скоро станет лень рассчитывать PageRank при каждом "воображаемом" изменении внешнего PageRank (P 0). Поэтому рассмотрим общий случай и выразим PR страниц как функции от P 0 -

В дальнейшем будем рассчитывать PageRank страниц как функции от входящего PR. Это позволит выделить ту компоненту PageRank, которая увеличивается по мере раскрутки, и отделить "остатки" в виде констант, величина которых порядка единицы. А солипсистскими методами расчета пользоваться на будем - мы ведь не одни в Интернете...

Функциональный метод расчета PageRank

Итак, будем рассчитывать PageRank страниц сайта как функцию от внешнего, "входящего" PageRank. Для этого нужны: уравнение (1) и представление об эквивалентности страниц одного типа. Пример-

На сайте, который приведен ниже, 3 нижних страницы эквивалентны между собой во всех смыслах. Соответственно, все они будут иметь одинаковый PageRank (P 2). Головная страница отличается от них и имеет PR=P 1 .

Запишем уравнения для страниц вида 1 и вида 2:

P 1 =0.15+0.85*(P 0 +3P 2)
- на страницу вида 1 ссылаются 3 страницы вида 2 , на каждой из которых есть одна ссылка.

P 2 =0.15+0.85*(P 1 /3)
- на страницу вида 2 ссылается страница вида 1 , на которой есть 3 ссылки.

Решая эту систему, получаем-

P 1 =0.15*(1+3*0.85)/(1-0.85^2)+0.85/(1-0.85^2)*P 0 =1.92+3.06*P 0
P 2 =0.69+0.87*P 0

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

Откуда берется PageRank?

Поль Дирак выдвигал предположение, что существует оптимальное расстояние, с которого лучше всего наблюдать женское лицо. Действтительно: на нулевом расстоянии, равно как и на бесконечном, удовольствие от созерцания стремится к нулю. В то же время, на промежуточном расстоянии оно явно не нулевое. Значит, между нулевым и бесконечным расстоянием существует максимум функции Удовольствие=f(Расстояние)

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

Случай 1: Все страницы в Интернете замкнуты в "кольцо" - на каждой есть только одна ссылка на соседа, и только одна входящая ссылка.
Результат:

Случай 2: Все страницы в Интернете перелинкованы друг с другом - на каждой из N страниц есть ссылки на всех N-1 соседей, и столько же входящих ссылок (N-1).
Результат: PageRank равен единице для всех страниц.

Откуда же берется большой PageRank?

Ответ: из неоднородности распределения ссылок по страницам. Дело в том, что все страницы сети были эквивалентны , что привело к одинаковому значению PageRank. Но если в однородном Интернете 2 страницы "обменяются ссылками", их PageRank увеличится. А у всего остального Интернета - чуть-чуть, но уменьшится. Таким образом, те, кто обмениваются ссылками, "стягивают одеяло на себя".

Надо сказать, что приведенный выше функциональный метод чуть-чуть неточен. Дело в том, что он не учитывает изменения среднего PageRank сети при появлении рассмотренного сайта. На сайте средний PageRank не равен единице, в отличие от Интернета, поэтому после проведенного расчета нужно пересчитать PR всех страниц в сети:

PR i new =PR i old *(Средний PR в интернете без вашего сайта)/(Средний PR в интернете, включая ваш сайт)

Но, поскольку суммарный PR по Интернету никто не знает, делать этого мы не будем. В любом случае эти изменения мизерные, но именно они и являются тем самым "стягиванием одеяла на себя ".

Промежуточные выводы

• Мало смысла в расчете PageRank страниц без учета "внешнего" PageRank
• Нормировка PageRank на единицу работает только в глобальном масштабе, но не в пределах одного сайта
• Значения PageRank порядка единицы очень малы и неинтересны для анализа. Основной интерес представляет передача потока PageRank от одной страницы к другой
guest

найти еще статьи

Рассчитываемая от количества и качества ссылок на эту страницу - как внешних, так и внутренних.

Расчет PageRank

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

PR(A) = (1 – d) + {PR(T1)/C(T1) + + PR(Tn)/C(Tn)}d (Назовем ее "формула №1")

Чтобы дать необходимые пояснения по приведенным в формуле символам, следует принять, что многие величины и обозначения, которые использует Google для расчета PR, являются его коммерческим, запатентованным секретом. Поэтому ниже будут даны предположительные пояснения, выведенные сообществом оптимизаторов экспериментальным путем.

• d - так называемый демпфирующий коэффициент, отображающий «количество авторитетности», передаваемое страницей-донором (источником ссылки) странице-акцептору (для которой рассчитывается PR). Величина коэффициента засекречена поисковиком, но наблюдения показывают, что с определенной точностью ее можно принять равной 0,85 (то есть 85% передаваемой авторитетности). По другим сведениям, демпфирующий коэффициент показывает вероятность перехода с донорской страницы на акцептор по установленной ссылке. Несмотря на отличие определений, d в этом случае также считают равным 0,85.
• n - количество страниц, на которых установлены ссылки на ту, для которой рассчитывается PR.
• С - общее количество внешних ссылок, установленных на донорской странице.
• Т (от 1 до n) - номера ссылающихся страниц.

ToolBar PageRank

В силу огромного количества страниц, размещенных в сети интернет, числовые значения PR, выраженные в абсолютных величинах, не являются удобным инструментом для быстрой оценки важности (такая оценка необходима, к примеру, при принятии решения об установке гиперссылки на определенной площадке). Гораздо удобнее в этом случае использовать предлагаемый Google ToolBar PageRank . Это специальная надстройка для браузеров , показывающая важность сайта в виде числа из интервала от 1 до 10. Рассчитывается TLPR по формуле:

TLPR = log base (PR) a

Точного значения основания логарифма base , зависящего от количества страниц в интернете, не существует, а формула его вычисления также является секретом поисковика. Однако, благодаря наблюдениям, его можно считать близким к числу 7. Точно так же значение коэффициента a из промежутка (0;1] берут 1. Таким образом, с достаточно большой точностью, «тулбарную» важность страницы, которая будет отображаться в браузерах пользователей, можно рассчитать как:

TLPRlog 7 (PR)

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

Наращивание PageRank посредством внутренней перелинковки

Формула расчета PageRank

Исходя из формулы ранжирования (формула №1) , можно утверждать, что минимальный PR любой страницы не может быть равным нулю, или же отрицательным. Если принять, что d = 0,85 , то 1 – d = 0,15 . Отсюда вывод: PR min = 0,15 (сумма в фигурных скобках в формуле №1 = 0).

Таким образом, даже для совершенно нового сайта со значительным количеством страниц и без внешних ссылок, благодаря грамотной

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

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

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

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

Объяснение:

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

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

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

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

И вот как:

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

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

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

1. Доктор Стефано Аллесина (Stefano Allesina) из Чикагского университета применил PageRank в сфере экологии, чтобы определить, какие из особей являются жизненно важными для поддержания экосистемы.
2. Twitter разработал WTF (Who-to-Follow) – персонализированный вариант рекомендательного движка, основанного на PageRank, показывающий список людей, на которых стоит подписаться.
3. Бин Жэнь (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 от Google.

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

Для чего же нужен PageRank? Ведь он не влияет на релевантность.
Веб-мастерам он необходим для увеличение стоимости размещения ссылок на их ресурсы. Если цена ссылки на страничке (не главной) с PR = 0 стоит максимум до 10 центов, то с PR = 4 стоит в разы больше.
Также, высокий уровень PageRank свидетельствует про авторитетность страницы, ее полного восприятия поисковой системой Google. Совокупность таких страниц позволяет Google формировать тематическое мнение про ресурс. Не буду утверждать, но я думаю что Google довольно часто не найдя конкретной запрошеной информации, выдает в ответе близке тематические ресурсы и соответсвенно ранжирует ее в зависимости от уровня PageRank. Как бы подсказывая пользователю где он бы мог найти интересующую его информацию.

Как вычислить PageRank?
Чтобы вычислить PageRank для страницы, необходимо учесть все внутренние и внешние ссылки на эту страницу:
- чем больше внешних ссылок на страницу, тем больше веса PageRank передается этой странице;
- чем больше внутренних ссылок на странице (в том числе внешние на другие ресурсы), тем больше вес PageRank распыляется по каждой ссылке равномерно. Таким образом все ссылки получат одинаковый вес.

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

Для вычисления PageRank для страницы можно использовать следующие уравнение:

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

PR() - PageRank страницы в виде числового числа (число с плавающей точкой);
A - страница PageRank которой мы определяем;
t1...tn - страницы, ссылающейся на страницу A;
C - количество исходящих ссылок со страницы А;
d - коэффициент затухания, обычно принимаемый 0,85.

Страница передает значение PageRank всем страницам, на которую она ссылается. При этом, значение PageRank вычисляется как собственна величина PageRank этой страницы умноженая на 0,85. Потом, эта величина распределяется равномерно между всеми страницами, на которые она ссылается.

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

Количество ссылок:	PageRank страниц, которые ссылаются на нашу:
	0	1	2	3	4	5	6	7	8	9	10
1	0	0	0	+1	+2	+3	+4	+5	+6	+7	+8
4	0	0	+1	+2	+3	+4	+5	+6	+7	+8	+9
19	0	+1	+2	+3	+4	+5	+6	+7	+8	+9	+10
101	+1	+2	+3	+4	+5	+6	+7	+8	+9	+10	-
555	+2	+3	+4	+5	+6	+7	+8	+9	+10	-	-
3 055	+3	+4	+5	+6	+7	+8	+9	+10	-	-	-
16 803	+4	+5	+6	+7	+8	+9	+10	-	-	-	-
92 414	+5	+6	+7	+8	+9	+10	-	-	-	-	-
508 277	+6	+7	+8	+9	+10	-	-	-	-	-	-
2 795 522	+6	+7	+8	+9	+10	-	-	-	-	-	-
15 375 379	+7	+8	+9	+10	-	-	-	-	-	-	-
84 564 584	+8	+9	+10	-	-	-	-	-	-	-	-
449 527 525	+9	+10	-	-	-	-	-	-	-	-	-

Проверить значение PR страниц можно на