The PageRank formula

We create PageRank™ (PR for short) by adding a "damping factor" to the NR* formula. The damping factor d is a fixed decimal value, 0≤d≤1 (e.g., d=0.85).

The PR formula:
For each node x∈V:
PRi(x) = (1-d) + d *
(Σ
     y∈InN(x)
 (PR(i-1)(y) / Outdegree(y))
)
 

Besides renaming NR* to PR, the only difference between the NR* and PR formulas is the use of the damping factor d. The meaning of the damping factor is subtle, so we first note what happens if we choose the most extreme possible values of d:

  • If d=1 then PR and NR* are exactly the same formula.
  • If d=0 then PRi(x) = 1 and the rest of the formula is irrelevant.

Example: We will calculate iterations 0-5 of PR, using d=0.85 and the same graph as before:

centrality

Node x
 Outdegree(x)
InN(x) PR0(x) PR1(x) PR2(x) PR3(x) PR4(x) PR5(x)
1  2{3,5} 1 0.858 0.678 0.686 0.719 0.715
2  2{4,1} 1 1.425 1.606 1.529 1.518 1.513
3  2{2,5} 1 0.858 0.919 0.978 0.953 0.955
4  1{2,1,5} 1 1.283 1.283 1.266 1.245 1.261
5  3{3} 1 0.575 0.515 0.540 0.566 0.555

The PR scores are very similar to the NR* scores. Using a spreadsheet, we can program the above calculation with a desired precision of 0.001 and observe convergence after 13 iterations. Node 2 is still the most influential node. The PR values are

  • PR13(1) = 0.713
  • PR13(2) = 1.521
  • PR13(3) = 0.954
  • PR13(4) = 1.257
  • PR13(5) = 0.555
< Prev   Next >
 
Joomla Templates by Joomlashack