Python Реализация PageRank - PullRequest
Новая
       6

Python Реализация PageRank

1 голос
/ 17 октября 2010

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

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

1 Ответ

8 голосов
/ 17 октября 2010

Я постараюсь дать простое объяснение (определение) алгоритма PageRank из моих личных заметок.

Допустим, страницы T1, T2, ... Tn указывают на страницу A, затем 

PR(A) = (1-d) + d * (PR(T1) / C(T1) + ... + PR(Tn) / C(Tn))

, где

  • PR (Ti) - PageRank Ti
  • C (Ti) - количество исходящих ссылок со страницы Ti
  • d - это коэффициент сброса в диапазоне 0

Каждый PR (x) может иметь начальное значение 1 , и мы корректируем ранги страниц, повторяя алгоритм ~ 10-20 раз для каждой страницы.

Пример для страниц A, B, C: 

   A <--> B
   ^     /
    \   v
      C

Раунд 1
A = 0,15 + 0,85 (1/2 + 1/1) = 1,425
B = 0,15 + 0,85 (1/1) = 1
С = 0,15 + 0,85 (1/2) = 0,575

сумма раунда = 3

Раунд 2
A = 0,15 + 0,85 (1/2 + 0,575) = 1,06375
B = 0,15 + 0,85 (1,425) = 1,36125
С = 0,15 + 0,85 (1/2) = 0,575

сумма раунда = 3

Раунд 3
A = 0,15 + 0,85 (1,36125 / 2 + 0,575) = 1,217
B = 0,15 + 0,85 (1,06375) = 1,054
C = 0,728

сумма раунда = 3

...

...