Keener's method

Keener's method is a recursive technique based on Perron-Frobenius theorem. Let $S_{i,j}$ be the number of points, or any other relevant statistics, that $i$ scores against $j$ and $A_{i,j}$ be the strength of $i$ compared to $j$. The strength $A_{i,j}$ can be interpreted as the probability that $i$ will defeat team $j$ in the future. For instance, $$A_{i,j} = S_{i,j} / (S_{i,j} + S_{j,i})$$ or, using Laplace's rule of succession, $$A_{i,j} = (S_{i,j} + 1) / (S_{i,j} + S_{j,i} + 2).$$ Notice that in both cases $0 \leq A_{i,j} \leq 1$ and $A_{i,j} + A_{j,i} = 1$.

The Keener's rating $r$ is the solution of the following recursive equation: $$A r = \lambda r,$$ where $\lambda$ is a constant and $A$ is the team strength matrix, or $$r_i = \frac{1}{\lambda} \sum_j A_{i,j} r_j.$$ Hence, the thesis of Keener is that team $i$ is strong if it defeated strong teams.

This is in fact eigenfactor centrality applied to strength matrix $A$. Assuming that matrix $A$ is nonnegative and irreducible (or equivalently that the graph of $A$ is connected), Perron-Frobenius theorem guarantees that a rating solution exists.

The following user-defined function keener computes the Keener's method:


# Keener
# ASSUMPTION: graph of A is strongly connected
# INPUT
# matches: matches data frame
# teams: team names
# OUTPUT
# r: Keener rating 
# value = eigenvalue
# A: match matrix
# g: match graph
keener = function(matches, teams) {
  # number of teams
  n = length(teams)
  
  # number of matches
  m = dim(matches)[1]
  
  # match matrix
  A = matrix(0, nrow=n, ncol=n, byrow=TRUE)
  
  # populate match matrix
  for (i in 1:m) {
    p = matches[i,"team1"]
    q = matches[i,"team2"]
    s1 = matches[i, "score1"]
    s2 = matches[i, "score2"]
    A[p,q] = (s1 + 1) / (s1 + s2 + 2);
    A[q,p] = (s2 + 1) / (s1 + s2 + 2);
  }
  
  # check assumptions
  g = graph_from_adjacency_matrix(A, mode="directed", weighted=TRUE)
  if (!is.connected(g, mode="strong")) {
    cat("The graph is not strongly connected")
    return(NULL)
  }
  
  
  e = eigen(A)
  v = e$values[1]
  r = Re(e$vectors[,1])
  if (r[1] < 0) {
    r = -r
  }
  names(r) = teams
  V(g)$teams = teams
  return(list(r = r, value = v, A = A, g = g))
}