PageRank

Rank the nodes of a directed graph with PageRank, using power iteration.

PageRank imagines a surfer who follows a random outgoing link with probability d, and jumps to a random node with probability 1 - d. A node's rank is the long-run fraction of time the surfer spends on it. Being linked from important nodes makes a node important.

A[i, j] = 1 means there is a link from node i to node j. Start with r = 1 / n everywhere and repeat:

r_new[j] = (1 - d) / n + d * ( sum over i linking to j of r[i] / out_degree[i]
                               + sum over dangling i of r[i] / n )

A dangling node has no outgoing links. Its rank is spread evenly over all nodes, so that no rank is lost. Stop when the sum of absolute changes is below tol.

Function signature

def pagerank(A, d=0.85, tol=1e-10):

Example

Input

A = np.array([[0, 1, 1],
              [0, 0, 1],
              [1, 0, 0]])
pagerank(A)

Output

array([0.38778971, 0.21481063, 0.39739966])

Reasoning

Node 2 is linked from both other nodes, so it ranks highest. Node 0 has only one incoming link, but that link is the only one leaving node 2, so node 0 gets all of node 2's rank and ranks nearly as high. Node 1 gets only half of node 0's rank.

Constraints and notes

• The ranks are positive and sum to 1.
• With d = 0 every node has rank 1 / n.