pagerank.py

from typing import Dict, List

def pagerank(G: Dict[int, List[int]], v: Dict[int, float] = None,
            alpha: float = 0.85, max_iter: int = 1000,
            tol: float = 10e-12) -> Dict[int, float]:
    # Number of nodes in the graph
    n = len(G)
    # Removes self loops from the graph
    for i in G:
        if i in G[i]:
            G[i].remove(i)
    # If v is not provided defaults to the equiprobability vector
    if (v is None):
        v = dict.fromkeys(G, 1 / n)
    # Else normalizes v to sum to 1
    else:
       s = sum(v.values())
       v = dict((k, x / s) for k, x in v.items())
    # Starting vector
    y = dict.fromkeys(G, 1 / n)
    # The out-degree is the number of neighbors of a node
    outdeg = lambda i: len(G[i])
    # Iterates until convergence
    for _ in range(max_iter):
        err: float = 0.0
        for i in G:
            s = sum(y[j]/outdeg(j) for j in G.keys() if (i in G[j]))
            y_new = v[i] + alpha * s
            # Computes the L1 norm without explicitly memorize the previous iteration
            err += abs(y_new - y[i])
            y[i] = y_new
        if (err < tol):
            norm = sum(y.values())
            z = dict((k, v / norm) for k, v in y.items())
            return z
    raise Exception(f"PageRank did not converge in {max_iter} iterations.")