Webwhompers

Here we present our own NetRank algorithm as a simplified version of PageRank™. NetRank and PageRank™ accept exactly the same input: a directed graph. They also provide the same kind of output -- influence scores for all the nodes of the graph -- although they compute slightly different values for these scores.

NetRank has two outstanding properties relative to PageRank™:

• NetRank captures the most important feature of PageRank™ that improves on indegree: Votes from high-ranked pages are worth more than votes from low-ranked pages.
• NetRank is much easier to compute than PageRank™ -- mostly because NetRank ignores all the other ways that PageRank™ improves on indegree as a measure of influence.

Example: We demonstrate the NetRank calculation using the following directed graph G=(V,E):

We write NR to denote NetRank. The calculation of NR proceeds iteratively. During iteration i, the calculation of NR_i improves upon the prior calculation of NR_(i-1). We write NR_i(x) to denote the NetRank value of node x during the i^th iteration of the calculation.

Iteration 0: To get the NetRank calculation started, we begin with NR₀(x) = 1 for every node x. Below we redraw G and write each NR₀ value inside the corresponding node.

Iteration 1: For each node x, NR₁(x) is the sum of the NR₀ scores of all the nodes that vote for x:

• NR₁(1) = NR₀(2) + NR₀(3) = 1 + 1
• NR₁(2) = NR₀(1) = 1
• NR₁(3) = NR₀(2) = 1

Below is G with each NR₁ value drawn inside the corresponding node. Note that for each node x, NR₁(x) equals the indegree of x. NR₁ counts votes and gives every vote equal weight.

Iteration 2: For each node x, NR₂(x) is the sum of the NR₁ scores of all the nodes that vote for x:

• NR₂(1) = NR₁(2) + NR₁(3) = 1 + 1
• NR₂(2) = NR₁(1) = 2
• NR₂(3) = NR₁(2) = 1

NR₂ counts votes, which are then weighted according to the rank of who cast each vote. NR₁ is used as the basis for weighting. Here is G with each NR₂ value drawn inside the corresponding node.

Iteration 3: For each node x, NR₃(x) is the sum of the NR₂ scores of all the nodes that vote for x:

• NR₃(1) = NR₂(2) + NR₂(3) = 2 + 1
• NR₃(2) = NR₂(1) = 2
• NR₃(3) = NR₂(2) = 2

NR₃ also counts weighted votes; however, the weighting of the votes is improved because NR₂ is used instead of NR₁. Here is G with each NR₃ value drawn inside the corresponding node.

Summary of Iterations 0-3: Each of the iterations above is a column in the following table:

Subsequent iterations: As we continue iterating, the pattern of computing NR_i by adding NR_(i-1) values remains the same. This pattern is determined by the original input to the algorithm: the nodes and edges of directed graph G. In our current example, the pattern can be drawn over the table of values. We also extend the table out to iteration 7:

The arrows show how values from one column move (or are added) to determine the values in the next column.