Webwhompers

Here again is our example input to the NetRank algorithm:

The table below shows iterations 0-7 of the NetRank calculation for this graph:

The scores are different and bigger with each iteration. Evidently these numbers will change and grow for as long as the NetRank calculation continues to iterate. These observations lead us to two questions:

• In what sense are the influence scores improving with each iteration?
• How many iterations must be done before the algorithm can stop?

We answer these questions by introducing normalization and convergence.

Normalization is a calculation that makes it easier to compare one column of numbers to another column. Normalizing column NR_i of the above table involves two steps: (1) add the numbers in column NR_i, and (2) divide each of the numbers in column NR_i by that sum.

The table above shows fractions to highlight the arithmetic of normalization. We write the exact same table a second time using decimals, in order to make it easier to compare one column of numbers to another (which is the point of normalization).

Convergence is a property illustrated by the above table of decimals. With each iteration, the changes from one column to the next become smaller and smaller. If we were to expand the above table to show column NR₁₆, we would see that, after normalization, NR₁₆(1) = 0.43, NR₁₆(2) = 0.32, and NR₁₆(3) = 0.25. Furthermore, the normalized NR_i values would never change (to the nearest 0.01) after iteration 16.

This point -- when further iterations of a calculation do not change the answer according to our desired level of precision (e.g., 0.01) -- is the point of convergence.

By normalizing the results of the NetRank calculation, we find that after enough iterations the values will converge. How many iterations is enough depends on (1) our desired level of precision, and (2) the input graph. More precision and larger graphs will require more iterations for convergence to occur.

Conclusion: Having started with the following input graph:

We have used NetRank to calculate the relative influence of each node of the graph.

• The normalized NetRank score of node 1 is 0.43
• The normalized NetRank score of node 2 is 0.32
• The normalized NetRank score of node 3 is 0.25