Excel lambda functions for PageRank

ragerank.txt

// --- Page Rank ---
// A set of formulas used to calculate pagerank
// from an adjacency matrix. For instance, with an adjacency
// matrix defined in cells C4:H9, a damping factor of 0.85 and
// 25 iterations, get the pagerank from:
//
//    =pagerank_from_adjacency_matrix(C4:H9, 0.85, 25)

// From a transition matrix  M, where
// 1 indicates a link otherwise leaving other 
// cells blank produce a normalised matrix
// where columns add up to one or zero. If no empty
// column in the input this produces a stochastic
// matrix.
//
// input example:
// 
// .  1  .  .
// 1  .  1  .
// 1  1  .  .
// .  .  .  .
//
// output:
//
// 0   0.5 0  0
// 0.5 0   1  0
// 0.5 0.5 0  0
// 0   0   0  0
//
// input:
//   M - an adjacency matrix with links marked by '1', otherwise
//   cells blank or '0' if no link.
normalise_by_column = lambda(M, 
  let(
    // fill in the zeros if missing
    filled, M + sequence(ROWS(M), COLUMNS(M), 0, 0),
    colsums, BYCOL(M, lambda(col, SUM(col))),
    M_hat, IFERROR(filled / colsums, 0),
    M_hat
  )
);

// Calculate Google matrix for the PageRank process
// 
// example input M
//
// 0   0.5 0  0
// 0.5 0   1  0
// 0.5 0.5 0  0
// 0   0   0  0
//
// output for d = 0.85
//
// 0.0375	0.4625	0.0375	0.0375
// 0.4625	0.0375	0.8875	0.0375
// 0.4625	0.4625	0.0375	0.0375
// 0.0375	0.0375	0.0375	0.0375
//
// inputs:
//   M - an adjacency matrix normalised by column
//   d - the damping factor, normally 0.85
gmatrix = lambda(M, d, let(
    sM, normalise_by_column(M),
    d_delta, (1-d)/rows(sM),
    return, sM * d + d_delta,
    return
    )
);

// Calculate PageRank from a google matrix and an initial
// vector.
//
// inputs:
//   M - a Google Matrix
//   v - an initial vector, this should normally be dimension
//   rank(M) and comprise entries 1/rank(M)
//   n - the number if iterations
// Return: A vector of page ranks 
pagerank_from_gmatrix = lambda(M,v, n,
  if(n < 1,
    v,
    pagerank_from_gmatrix(M, MMULT(M, v), n-1))
);

// Get the Page Rank from an adjacency matrix
// 
// inputs:
//    M - An adjacency matrix
//    d - the damping factor, normally set to 0.85
//    n - number of iterations - 10 should be enough
//    for a small matrix that fits onto a single XL
//    sheet
pagerank_from_adjacency_matrix = LAMBDA(M, d, n,
  Let(
      gM, gmatrix(M, d),
      v, SEQUENCE(ROWS(M), 1, 1/ROWS(M), 0),
      pagerank_from_gmatrix(gM, v, n)
  )
);