Pagerank расчет: PageRank – формула расчета веса ссылки – Расчет PageRank — онлайн калькулятор

Содержание

PageRank – формула расчета веса ссылки

Вес ссылки – это степень влияния каждой ссылки на продвижение сайта в поисковой системе.

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

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

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

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

Формула PageRank , где

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

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

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

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

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


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

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

Вернуться назад: Что такое ссылка Читать далее: Как передается вес ссылки

 

 

Расчет PageRank - онлайн калькулятор

Расчет PageRank ©Бюро Погодаева
Количество ссылок со страниц с
PR равным индексу N

Терминология

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

HostRank - аналогичный фактор, но расчитывается для сайта в целом. Повышение HostRank отражается на ранжировании каждой страницы.

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


Наш блог

  • Накрутка лайков и подписчиков ВКОНТАКТЕ

    Накрутка лайков и подписчиков ВКОНТАКТЕ

    18:36 05/03/2020

    ВКонтакте – это отличная площадка для бизнеса или ведения личного блога. Для привлечения активной аудитории владельцы сообществ иногда накручивают собственные показатели.

  • Накрутка подписчиков и лайков в Инстаграме: ТОП-10 сервисов

    Накрутка подписчиков и лайков в Инстаграме: ТОП-10 сервисов

    14:48 05/03/2020

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

  • Лучшие конструкторы Landing Page 2020 г.

    Лучшие конструкторы Landing Page 2020 г.

    18:08 26/02/2020

    Конструктор лэндингов представляет собой онлайн-сервис для создания различных сайтов без знаний программирования и особых навыков. Я подготовил обзор 12 сервисов и выбрал лучший из них!

  • Хостинг для сайта - ТОП-10 лучших!

    Хостинг для сайта - ТОП-10 лучших!

    18:20 25/02/2020

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

Как правильно строить внутренние ссылки

telegram channel

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

Архитектура вашего сайта – структура и способ организации внутренних ссылок (например, ссылка на раздел «О нас» из основного меню на вашем сайте) – играет жизненно важную роль в навигации по сайту для пользователей и поисковой системы, а также влияет на ваше ранжирование.

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

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

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

Базовая архитектура сайта и навигационная внутренняя перелинковка

Есть два основных типа внутренних ссылок:

  1. Внутренние ссылки, которые формируют навигационную структуру вашего сайта;
  2. Второстепенные внутренние ссылки, которые находятся в контенте вашего сайта (в статьях и других местах, которые не являются частью навигационной структуры).

Первый шаг на пути к построению правильной внутренней перелинковки – это организация общих навигационных элементов и следование правильной структуре сайта. Я советую создавать классическую внутреннюю перелинковку и использовать силос-архитектуру Брюса Клэя как основу для внутренних ссылок. Это проверенная логичная структура сайта, которая работает.

Вот пример от Portent:

internalpr-1

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

Что такое PageRank?

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

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

Графическая интерпретация PageRank:

internalpr2

Внутренний PageRank?

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

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

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

Итак, приступим к подсчёту внутреннего PageRank для вашего сайта.

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

Шаг 1: Сканируем с помощью Screaming Frog

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

Начните с запуска Screaming Frog и сканирования вашего сайта. Когда сканирование закончится, выберите

Bulk Export > All Outlinks в верхнем меню, затем сохраните CSV-файл в удобной для вас директории:

internalpr3

CSV-файл содержит список всех внутренних ссылок вашего сайта. Мы будем использовать этот список, чтобы рассчитать внутренний PageRank.

Шаг 2: Считаем внутренний PageRank с помощью R

R — это бесплатный софт для статистических расчётов и построения графиков, работающий на различных платформах. Загрузите и установите его, если вы ещё не сделали этого.

Установите igraph библиотеку, запустив консоль R и выполнив команду:

install.packages(«igraph»)

Когда вы установите библиотеку, у вас появится возможность использовать код, который представлен ниже, в сочетании с результатами сканирования Screaming Frog для вашего сайта:

Просто используйте код выше и не забудьте сделать следующее:

  1. Указать путь к CSV-файлу Screaming Frog;
  2. Указать свой домен и TLD-расширение;
  3. Создать имя конечного файла, который будет содержать показатели внутреннего PageRank каждой страницы вашего сайта.

Примеры

Давайте рассмотрим на примере нескольких реальных сайтов.

Catalyst Digital

Наше агентство Catalyst Digital недавно обновило свой сайт после ребрендинга, и мы до сих пор устраняем ошибки. Поэтому я решил просканировать новый сайт и проверить внутренний PageRank.

Вот результат:

internalpr5

Если взглянуть на страницы сайта с точки зрения PageRank, мы увидим, что ТОПовой страницей является страница контактов. Это неправильно.

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

internalpr6

Внутренний PageRank, так же как и Google PageRank, учитывает сколько и, главное, КАКИЕ ссылки ведут на эту страницу. Несмотря на более высокий PageRank, количество ссылок на страницу контактов меньше.

Итак, проверим в Google запрос по нашему бренду:

internalpr7

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

Теперь, когда мы обнаружили проблему, мы можем пересмотреть архитектуру нашего сайта и устранить причину. Знание – сила.

Online Geniuses

Давайте проведём аналогичный тест на Online Geniuses (модерируемое мной онлайн-сообщество, посвящённое интернет-маркетингу) и посмотрим, что выйдет.

Вот результат, полученный в R:

internalpr8

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

Заключение

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

 

Подписаться на рассылку

Еще по теме:


internalpr8

Алина Крутоголова

Есть вопросы?

Задайте их прямо сейчас, и мы ответим в течение 8 рабочих часов.

internalpr8

Расчет PageRank | Растолкованный PageRank,

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

Когда Google был только исследовательским проектом, они [Брин и Пэйдж — прим. А. С.] написали статью, подробно описывающую формулу, которая определяет вес PageRank для страницы. Хотя они, возможно, уже не используют в точности эту формулу, она представляется достаточно корректной для сегодняшних целей. Вот она:

PR(A) = (1-d) + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn)),

где PR(A) — это вес PageRank страницы A (тот вес, который мы хотим вычислить),

D — это коэффициент затухания, который обычно устанавливают равным 0,85,

PR(T1) — вес PageRank страницы, указывающей на страницу A,

C(T1) — число ссылок с этой страницы,

PR(Tn)/C(Tn) означает, что мы делаем это для каждой страницы, указывающей на страницу A

Жуть! Для тех из вас, кто не является математиком, здесь есть полная информация по этой формуле — вы не можете просто вычислить вес PageRank за один прием, как показано тут. Чтобы вычислить вес PageRank страницы A вам понадобится знать веса PageRank всех страниц, указывающих на страницу A. Их веса PageRank будут частично зависеть от страницы A, указывающей на них, либо каких-то других страниц, ссылающихся на них. Какая глупая формула. Что она нам говорит, так это одну очень важную вещь о весе PageRank любой страницы.

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

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

 

Вначале мы не знаем, какие веса MiniRank у этих страниц, поэтому мы их просто присвоим. Для простоты, мы выберем число один. В результате диаграмма становится…

Все еще легко! Сейчас вспомните правила передачи веса. Вначале мы применяем коэффициент затухания. (Коэффициент затухания, в основном, говорит о том, что страница не может голосовать так, чтобы другая страница была столь же важна, как она сама. Это означает, что страницы, к которым труднее добраться в Web, менее важны.) Затем мы делим сохранившийся вес на число ссылок. Мы подсчитываем итоговый вес, который должен быть добавлен ко всем до единой страницам, перед тем как мы окончательно его прибавим.

Итак, глядя вначале на страницу A, видим, что значение веса MiniRank, доступное для передачи, после затухания равно 1 * 0,85 = 0,85. Со страницы ведут две ссылки, поэтому, по окончании итерации, мы добавим 0,425 к весу MiniRank страницы B и 0,425 к весу MiniRank страницы C. Мы не можем сделать это до тех пор, пока мы не рассчитали все ссылки страницы, потому что это повлияет на результаты.

Перейдем к странице B. Она содержит только одну ссылку. Поэтому, она передаст 1 * 0,85 = 0,85 странице C, когда мы сделаем все вычисления для ссылок.

Страница C также имеет одну ссылку. Поэтому она передаст вес 1 * 0,85 = 0,85 странице A.

Страница D имеет одну ссылку, поэтому она передает 0,85 странице C.

Сейчас мы можем добавить все суммы ко всем весам страниц.

Новые значения весов MiniRank показывают, сколь важна страница C. Но мы еще не завершили. Поскольку все страницы начали с одного значения, по правде говоря, мы вычислили только популярность в ссылках (link popularity). Суть PageRank и MiniRank такова, что страницам, на которые чаще ссылаются, следует получить больше голосов; поэтому мы должны проделать то же самое еще раз! На этот раз страница C имеет большее влияние, потому что ее текущий вес MiniRank выше.

Так, посмотрим на страницу A вначале. Ее текущий вес MiniRank равен 1,85. Величина MiniRank, доступная для передачи, после применения затухания составляет 1,85 * 0,85 = 1,5725. Есть две ссылки со страницы, поэтому по завершению итерации мы добавим 0,78625 к весу MiniRank страницы B и весу MiniRank страницы C.

Перейдем к странице B. У нее есть только одна ссылка. Следовательно, она передаст 1,425 * 0,85 = 1,21125 странице C, когда мы завершим все вычисления со ссылками.

Страница C также имеет одну ссылку, но при этом обладает огромным весом 3,125 MiniRank. Поэтому она передаст 3,125 * 0,85 = 2,65625 странице A.

Страница D имеет одну ссылку, поэтому она передает 0,85 странице C.

Мы получаем….

 

Мы уже можем видеть то, что следовало ожидать: страница C имеет наибольший вес MiniRank, страница A — следующий по величине. На практике нам нужно было бы повторить эти действия от 50 до 100 раз, чтобы гарантировать, что низкая точность предыдущих итераций сведена на нет. Просто!

Понравилось это:

Нравится Загрузка...

Растолкованный PageRank. Как рассчитывается Pagerank Расчет 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 достигается значительно сложнее

Как оптимизировать мой расчет PageRank?

В книге Программирование коллективного разума я нашел следующую функцию для вычисления PageRank:

def calculatepagerank(self,iterations=20):
    # clear out the current PageRank tables
    self.con.execute("drop table if exists pagerank")
    self.con.execute("create table pagerank(urlid primary key,score)")
    self.con.execute("create index prankidx on pagerank(urlid)")

    # initialize every url with a PageRank of 1.0
    self.con.execute("insert into pagerank select rowid,1.0 from urllist")
    self.dbcommit()

    for i in range(iterations):
        print "Iteration %d" % i
        for (urlid,) in self.con.execute("select rowid from urllist"):
            pr=0.15

            # Loop through all the pages that link to this one
            for (linker,) in self.con.execute("select distinct fromid from link where toid=%d" % urlid):
                # Get the PageRank of the linker
                linkingpr=self.con.execute("select score from pagerank where urlid=%d" % linker).fetchone()[0]

                # Get the total number of links from the linker
                linkingcount=self.con.execute("select count(*) from link where fromid=%d" % linker).fetchone()[0]

                pr+=0.85*(linkingpr/linkingcount)

            self.con.execute("update pagerank set score=%f where urlid=%d" % (pr,urlid))
        self.dbcommit()

Однако эта функция работает очень медленно из-за всех запросов SQL в каждой итерации

>>> import cProfile
>>> cProfile.run("crawler.calculatepagerank()")
         2262510 function calls in 136.006 CPU seconds

   Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.000    0.000  136.006  136.006 <string>:1(<module>)
     1   20.826   20.826  136.006  136.006 searchengine.py:179(calculatepagerank)
    21    0.000    0.000    0.528    0.025 searchengine.py:27(dbcommit)
    21    0.528    0.025    0.528    0.025 {method 'commit' of 'sqlite3.Connecti
     1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler
1339864  112.602    0.000  112.602    0.000 {method 'execute' of 'sqlite3.Connec 
922600    2.050    0.000    2.050    0.000 {method 'fetchone' of 'sqlite3.Cursor' 
     1    0.000    0.000    0.000    0.000 {range}

Поэтому я оптимизировал функцию и придумал это:

def calculatepagerank2(self,iterations=20):
    # clear out the current PageRank tables
    self.con.execute("drop table if exists pagerank")
    self.con.execute("create table pagerank(urlid primary key,score)")
    self.con.execute("create index prankidx on pagerank(urlid)")

    # initialize every url with a PageRank of 1.0
    self.con.execute("insert into pagerank select rowid,1.0 from urllist")
    self.dbcommit()

    inlinks={}
    numoutlinks={}
    pagerank={}

    for (urlid,) in self.con.execute("select rowid from urllist"):
        inlinks[urlid]=[]
        numoutlinks[urlid]=0
        # Initialize pagerank vector with 1.0
        pagerank[urlid]=1.0
        # Loop through all the pages that link to this one
        for (inlink,) in self.con.execute("select distinct fromid from link where toid=%d" % urlid):
            inlinks[urlid].append(inlink)
            # get number of outgoing links from a page        
            numoutlinks[urlid]=self.con.execute("select count(*) from link where fromid=%d" % urlid).fetchone()[0]            

    for i in range(iterations):
        print "Iteration %d" % i

        for urlid in pagerank:
            pr=0.15
            for link in inlinks[urlid]:
                linkpr=pagerank[link]
                linkcount=numoutlinks[link]
                pr+=0.85*(linkpr/linkcount)
            pagerank[urlid]=pr
    for urlid in pagerank:
        self.con.execute("update pagerank set score=%f where urlid=%d" % (pagerank[urlid],urlid))
    self.dbcommit()

Эта функция во много раз быстрее (но использует гораздо больше памяти для всех временных словарей), потому что она позволяет избежать ненужных запросов SQL в каждой итерации:

>>> cProfile.run("crawler.calculatepagerank2()")
     90070 function calls in 3.527 CPU seconds
Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.004    0.004    3.527    3.527 <string>:1(<module>)
     1    1.154    1.154    3.523    3.523 searchengine.py:207(calculatepagerank2
     2    0.000    0.000    0.058    0.029 searchengine.py:27(dbcommit)
 23065    0.013    0.000    0.013    0.000 {method 'append' of 'list' objects}
     2    0.058    0.029    0.058    0.029 {method 'commit' of 'sqlite3.Connectio
     1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler
 43932    2.261    0.000    2.261    0.000 {method 'execute' of 'sqlite3.Connecti
 23065    0.037    0.000    0.037    0.000 {method 'fetchone' of 'sqlite3.Cursor'
     1    0.000    0.000    0.000    0.000 {range}

Но можно ли еще больше уменьшить количество запросов SQL, чтобы ускорить работу функции? Обновление: исправлен отступ в calculatepagerank2().

python sql optimization pagerank Поделиться Источник asmaier     20 марта 2010 в 19:41

4 Ответов



2

Если у вас есть очень большая база данных (например, # records ~ # pages в WWW), использование базы данных таким образом, как это предлагается в книге, имеет смысл, потому что вы не сможете сохранить все эти данные в памяти.

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

for urlid, in self.con.execute('select rowid from urllist'):
    inlinks[urlid] = []
    numoutlinks[urlid] = 0
    pagerank[urlid] = 1.0

for src, dest in self.con.execute('select fromid, toid from link'):
    inlinks[dest].append(src)
    numoutlinks[src] += 1

Эта версия делает ровно 2 запроса вместо o (n^2) запросов.

Поделиться allyourcode     21 марта 2010 в 01:23



1

Я считаю, что большая часть времени тратится на эти SQL запроса:

for (urlid,) in self.con.execute("select rowid from urllist"):
    ...
    for (inlink,) in self.con.execute("select distinct fromid from link where toid=%d" % urlid):
        ...
        numoutlinks[urlid]=self.con.execute("select count(*) from link where fromid=%d" % urlid).fetchone()[0]            

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

  1. SELECT fromid,toid FROM link WHERE toid IN (SELECT rowid FROM urllist)
    и
  2. SELECT fromid,count(*) FROM link WHERE fromid IN (SELECT rowid FROM urllist) GROUP BY fromid

Затем вы можете перебрать результаты и построить inlinks, numoutlinks и pagerank .

Вы также можете извлечь выгоду из использования collections.defaultdict :

import collections
import itertools
def constant_factory(value):
    return itertools.repeat(value).next

Следующее затем делает inlinks диктом множеств. Наборы уместны, так как вам нужны только отдельные URL-адреса

inlinks=collections.defaultdict(set)

И это делает pagerank диктом, значение по умолчанию которого равно 1.0:

pagerank=collections.defaultdict(constant_factory(1.0))

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

Итак, вместе взятые, то, что я предлагаю, будет выглядеть примерно так:

import collections
def constant_factory(value):
    return itertools.repeat(value).next
def calculatepagerank2(self,iterations=20):
    # clear out the current PageRank tables
    self.con.execute("DROP TABLE IF EXISTS pagerank")
    self.con.execute("CREATE TABLE pagerank(urlid primary key,score)")
    self.con.execute("CREATE INDEX prankidx ON pagerank(urlid)")

    # initialize every url with a PageRank of 1.0
    self.con.execute("INSERT INTO pagerank SELECT rowid,1.0 FROM urllist")
    self.dbcommit()

    inlinks=collections.defaultdict(set)

    sql='''SELECT fromid,toid FROM link WHERE toid IN (SELECT rowid FROM urllist)'''
    for f,t in self.con.execute(sql):
        inlinks[t].add(f)

    numoutlinks={}
    sql='''SELECT fromid,count(*) FROM link WHERE fromid IN (SELECT rowid FROM urllist) GROUP BY fromid'''
    for f,c in self.con.execute(sql):
        numoutlinks[f]=c

    pagerank=collections.defaultdict(constant_factory(1.0))
    for i in range(iterations):
        print "Iteration %d" % i
        for urlid in inlinks:
            pr=0.15
            for link in inlinks[urlid]:
                linkpr=pagerank[link]
                linkcount=numoutlinks[link]
                pr+=0.85*(linkpr/linkcount)
            pagerank[urlid]=pr
    sql="UPDATE pagerank SET score=? WHERE urlid=?"
    args=((pagerank[urlid],urlid) for urlid in pagerank)
    self.con.executemany(sql, args)
    self.dbcommit()

Поделиться unutbu     21 марта 2010 в 01:27



0

Есть ли у вас достаточно RAM, чтобы удерживать разреженную матрицу (fromid, toid) в какой-то форме? Это позволило бы провести большую оптимизацию (с большими алгоритмическими изменениями). По крайней мере, кэширование в памяти (fromid, numlinks) , которое вы теперь делаете с select count(*) в вашем самом внутреннем цикле, должно помочь (я бы предположил, что кэш, будучи O(N) в пространстве, если вы имеете дело с N URLs, с большей вероятностью поместится в памяти).

Поделиться Alex Martelli     21 марта 2010 в 01:06



0

Я отвечаю на свой собственный вопрос, так как в конце концов выяснилось, что смесь всех ответов лучше всего подходит для меня:

    def calculatepagerank4(self,iterations=20):
    # clear out the current PageRank tables
    self.con.execute("drop table if exists pagerank")
    self.con.execute("create table pagerank(urlid primary key,score)")
    self.con.execute("create index prankidx on pagerank(urlid)")

    # initialize every url with a PageRank of 1.0
    self.con.execute("insert into pagerank select rowid,1.0 from urllist")
    self.dbcommit()

    inlinks={}
    numoutlinks={}
    pagerank={}

    for (urlid,) in self.con.execute("select rowid from urllist"):
        inlinks[urlid]=[]
        numoutlinks[urlid]=0
        # Initialize pagerank vector with 1.0
        pagerank[urlid]=1.0

    for src,dest in self.con.execute("select distinct fromid, toid from link"):
        inlinks[dest].append(src)
        numoutlinks[src]+=1          

    for i in range(iterations):
        print "Iteration %d" % i

        for urlid in pagerank:
            pr=0.15
            for link in inlinks[urlid]:
                linkpr=pagerank[link]
                linkcount=numoutlinks[link]
                pr+=0.85*(linkpr/linkcount)
            pagerank[urlid]=pr

    args=((pagerank[urlid],urlid) for urlid in pagerank)
    self.con.executemany("update pagerank set score=? where urlid=?" , args)
    self.dbcommit() 

Поэтому я заменил первые два цикла, как было предложено allyourcode, но в дополнение также использовал executemany(), как и в решении от ˜unutbu . Но в отличие от ˜unutbu я использую генераторное выражение для args, чтобы не тратить слишком много памяти, хотя использование понимания списка было немного быстрее. В конце концов рутина была в 100 раз быстрее той что предлагалась в книге:

>>> cProfile.run("crawler.calculatepagerank4()")
     33512 function calls in 1.377 CPU seconds
Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.004    0.004    1.377    1.377 <string>:1(<module>)
     2    0.000    0.000    0.073    0.036 searchengine.py:27(dbcommit)
     1    0.693    0.693    1.373    1.373 searchengine.py:286(calculatepagerank4
 10432    0.011    0.000    0.011    0.000 searchengine.py:321(<genexpr>)
 23065    0.009    0.000    0.009    0.000 {method 'append' of 'list' objects}
     2    0.073    0.036    0.073    0.036 {method 'commit' of 'sqlite3.Connectio
     1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler
     6    0.379    0.063    0.379    0.063 {method 'execute' of 'sqlite3.Connecti
     1    0.209    0.209    0.220    0.220 {method 'executemany' of 'sqlite3.Conn
     1    0.000    0.000    0.000    0.000 {range}

Следует также иметь в виду следующие проблемы:

  1. Если вы используете форматирование строк с помощью %f вместо использования заполнителя ? для построения оператора SQL, вы потеряете точность (например, я получил 2.9796095721920315, используя ? , но 2.9796100000000001, используя %f .
  2. Повторяющиеся ссылки с одной страницы на другую рассматриваются как только одна ссылка в алгоритме default PageRank. Однако решение из книги этого не учло.
  3. Весь алгоритм из книги имеет недостатки: причина в том, что в каждой итерации оценка pagerank не сохраняется во второй таблице. Но это означает, что результат итерации зависит от порядка перебираемых страниц, и это может довольно сильно изменить результат после нескольких итераций. Чтобы решить эту проблему, нужно либо использовать дополнительную таблицу / словарь для хранения pagerank для следующей итерации, либо использовать совершенно другой алгоритм, например Power Iteration .

Поделиться asmaier     24 марта 2010 в 22:25


Похожие вопросы:


Внедрение PageRank для исследований

После прочтения теории алгоритма PageRank с этого сайта я хотел бы поиграть с ним. Я пытаюсь реализовать это в Java. Я имею в виду, что я хотел бы играть с PageRank в деталях (например, давать...


Улучшение pagerank с помощью seo-дружественный url

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


Как нормализовать PageRank баллов

Я запускаю PageRank на группе узлов, где каждый узел имеет свойство year . Как я могу рассчитать средние значения всех баллов PageRank в зависимости от свойства year ? То есть, если есть 100 узлов с...


Как pagerank рассчитывается распределенным способом?

Я понимаю идею PageRank и реализовал ее(читая книгу Программирование коллективного разума). Но я читал, что он может быть распределен по нескольким серверам (как я думаю, google делает). Я немного...


Как получить google pagerank от delphi

Кто-нибудь может показать пример кода, как получить google pagerank от delphi ? например, с использованием INDY. Я имею в виду без использования внешнего скрипта PHP. Поэтому я имею в виду прямой...


Оценка PageRank вычислительной

В настоящее время я работаю над алгоритмом TextRank, который использует PageRank. Мне было интересно, как PageRank учитывает вес ребра при расчете баллов? Я работаю с Python для реализации моего...


Как использовать алгоритм PageRank в JUNG?

Я использую JUNG в качестве инструмента для визуализации сетевого графика и вычисления сетевых атрибутов (например: indegree, outdegree и pagerank). Я знаю, что JUNG уже реализовал алгоритм...


Google PageRank-насколько это важно?

Мы просто пытаемся оптимизировать наши процедуры SEO и читали о том, что Google pageranking не является фактором в эти дни. Но означает ли это, что ссылка с сайта с pagerank 0 будет иметь такое же...


Получение Хорошего Google PageRank

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


Получение PageRank

Как я могу получить pagerank любой страницы, индексированной google? Есть ли у Google какой-либо API или страница для этого?


Как рассчитать будущий PageRank страницы сайта

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

Как рассчитать PageRank

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

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

Расчет PageRank ведется сложными математическими формулами, которые учитывают множество факторов.

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

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

Работать с таблицей интуитивно просто: в столбце слева смотрите нужное будущее значение PR своего сайта. А справа — количество необходимых для этого ссылок.

Количество страниц с нужным PR для накрутки своих показателей
нужны ссылки со страниц с PR 1 2 3 4 5 6 7 8 9 10
чтобы получить PR своей страницы 2 101 18 3 1 1 1 1 1 1 1
чтобы получить PR своей страницы 3 555 101 18 3 1 1 1 1 1 1
чтобы получить PR своей страницы 4 3055 555 101 18 3 1 1 1 1 1
чтобы получить PR своей страницы 5 16803 3055 555 101 18 3 1 1 1 1
чтобы получить PR своей страницы 6 92414 16803 3055 555 101 18 3 1 1 1
чтобы получить PR своей страницы 7 0.5млн 92414 16803 3055 555 101 18 3 1 1
чтобы получить PR своей страницы 8 2,8млн 0,5млн 92414 16803 3055 555 101 18 3 1
чтобы получить PR своей страницы 9 15млн 2,8млн 0,5млн 92414 16803 3055 555 101 18 3
чтобы получить PR своей страницы 10 84млн 15млн 2,8млн 0,5млн 92414 16803 3055 555 101 18

Отправить ответ

avatar
  Подписаться  
Уведомление о