Webwhompers

Recall the NetRank calculation before we introduced normalization and convergence. For our 3-node example graph, we represented this calculation with the following table:

To write the NetRank algorithm (which computes the values in the above table), we need a mathematical way to say, "everyone who has voted for node x." We define InNeighhorhood for this purpose. Given a directed graph G=(V,E) and a node x, the InNeighborhood of x is:

InN(x) = {y: (y,x) ∈ E} = the set of all nodes with directed edges into x

We can now state the NetRank algorithm:

NetRank Algorithm:

Input:

1. Directed graph G=(V,E)

Output:

1. Influence scores for nodes in V

Steps:

1. For each node x∈V: NR₀(x)=1
2. i = 1

3. For each node x∈V:

   NRi(x) =

   Σ y∈InN(x)

   (NR(i-1)(y))

4. If normalized NR_i values have converged, then we're done
5. i = i + 1
6. Go to step 3

Example: We will calculate iterations 0-5 of NetRank using the graph from the very beginning of this chapter:

The table below includes a column for the InNeighborhood of each node. As we see in step 3 of the algorithm above, this is exactly the information that determines the pattern of computing NR_i from NR_(i-1). When constructing a NetRank table, writing this information explicitly helps organize the subsequent arithmetic.

The NetRank scores above have not been normalized. Skipping the process of normalization makes it impossible to detect convergence but easy to do a pre-specified number of iterations manually (without a calculator).

Node 4 is the most influential node according to NR₅. Using a spreadsheet, we can program the above calculation and include normalization. With a desired precision of 0.001, we observe convergence after 34 iterations. Node 4 is still the most influential node. The normalized NetRank values are

• normalized NR₃₄(1) =  0.166
• normalized NR₃₄(2) =  0.248
• normalized NR₃₄(3) =  0.195
• normalized NR₃₄(4) =  0.285
• normalized NR₃₄(5) =  0.107