Dividing by outdegree: the NR* formula

One way to represent the NetRank calculation is with the NR formula:

For each node x∈V:
NRi(x) =
Σ
y∈InN(x)
 (NR(i-1)(y))

The NR formula is taken from step 3 of of the NetRank algorithm. In order to transform the NetRank calculation into PageRank™, we can keep the basic iterative structure of the NetRank algorithm, but we must make two changes to the NR formula:

  1. Accounting for the following feature of PageRank™: For each page, the weight of each individual vote cast by that page decreases according to the total number of votes cast by that page.
  2. Accounting for the "damping factor" that is built into PageRank™

The first change gives us the NR* formula:

For each node x∈V:
NR*i(x) =
Σ
y∈InN(x)
 (NR*(i-1)(y) / Outdegree(y))

Besides renaming NR to NR*, the only difference between the NR and NR* formulas is that NR* divides the weight of each vote by the outdegree of the node casting that vote. This models the desired effect: the weight of each individual vote cast by a page decreases according to the total number of votes cast by that page.

Example: We will calculate iterations 0-5 of NR* with the same graph we just used to demonstrate NR:

centrality

The table below includes a column for the outdegree of each node. Because each NR*i calculation adds fractions with different denominators (based on outdegree values), the arithmetic is too messy to do manually. We have used a spreadsheet to calculate the NR*1 - NR*5 values below.

Node x
 Outdegree(x)
InN(x) NR*0(x) NR*1(x) NR*2(x) NR*3(x) NR*4(x) NR*5(x)
1  2{3,5} 1 0.833 0.597
 0.597
 0.660 0.652
2  2{4,1} 1 1.500 1.750
 1.625
 1.604 1.594
3  2{2,5} 1 0.833 0.917
 1.014
 0.965 0.971
4  1{2,1,5} 1 1.333 1.333
 1.306 1.264 1.301
5  3{3} 1 0.500 0.417
 0.458
 0.507 0.483

The NR* scores above have not been normalized; however it appears that NR* scores will converge even without normalization. This convergence occurs because dividing by outdegree has an effect similar to that of normalization. In particular, dividing by outdegree limits how much the NR* values can grow -- unlike the endless growth of NR values that we have observed.

Note: Using NR* instead of NR gives us a different definition of the most influential node in our graph. Node 2 is the most influential node according to NR*5. Using a spreadsheet, we can program the above calculation with a desired precision of 0.001 and observe convergence after 28 iterations. Node 2 is still the most influential node. The NR* values are

  • NR*28(1) = 0.645
  • NR*28(2) = 1.613
  • NR*28(3) = 0.968
  • NR*28(4) = 1.290
  • NR*28(5) = 0.484

Previously we have seen that node 4 is most influential according to NR; it is second-most influential according to NR*.

Consider: Why does node 4 drop from most influential to second-most influential after we account for outdegree in the weighting of votes?

< Prev   Next >
 
Joomla Templates by Joomlashack