{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ranking by Reordering\n",
    "\n",
    "The problem of ranking a set of objects is ubiquitous not only in everyday life, but also for many scientific problems such as information retrieval, recommender systems, natural language processing, and drug discovery. This problem can be formulated as a 2-sided permutation Procrustes with single transformation.\n",
    "\n",
    "\n",
    "> **Permutation Procrustes 2-Sided with Single-Transformation**\n",
    ">\n",
    "> Given matrix $\\mathbf{A}_{n \\times n}$ and a reference $\\mathbf{B}_{n \\times n}$, find a permutation of rows/columns of $\\mathbf{A}_{n \\times n}$ that makes it as close as possible to $\\mathbf{B}_{n \\times n}$, i.e.,\n",
    ">\n",
    "\\begin{equation}\n",
    "   \\underbrace{\\text{min}}_{\\left\\{\\mathbf{P} \\left| {p_{ij} \\in \\{0, 1\\}\n",
    "               \\atop \\sum_{i=1}^n p_{ij} = \\sum_{j=1}^n p_{ij} = 1} \\right. \\right\\}}\n",
    "               \\|\\mathbf{P}^\\dagger \\mathbf{A} \\mathbf{P} - \\mathbf{B}\\|_{F}^2 \\\\\n",
    "\\end{equation}\n",
    "\n",
    "\n",
    "The code block below, we use the `procrustes` library to rank five American collegiate football teams, where each team plays one game against every other team, using their score-differentials as summarized below (data taken from A. N. Langville, C. D. Meyer, *Ranking by Reordering Methods*, Princeton University Press, 2012, Ch. 8, pp. 97–112). Here, each team is given a zero score for a game they lost (e.g., Duke lost to every other team) and the score difference is calculated for games won (e.g., Miami beat Duke by 45 points and UNC by 18 points). These results are also summarized in the square score-differential matrix $\\mathbf{A}$ in **Fig (i)**.\n",
    "\n",
    "| Team  | Duke | Miami | UNC | UVA | VT |\n",
    "|-------|------|-------|-----|-----|----|\n",
    "| Duke  | 0    | 0     | 0   | 0   | 0  |\n",
    "| Miami | 45   | 0     | 18  | 8   | 20 |\n",
    "| UNC   | 3    | 0     | 0   | 2   | 0  |\n",
    "| UVA   | 31   | 0     | 0   | 0   | 0  |\n",
    "| VT    | 45   | 0     | 27  | 38  | 0  |\n",
    "\n",
    "Before applying Procrustes, one needs to define a proper target matrix. Traditionally, the rank-differential matrix has been used for this purpose and is defined for $n$ teams as,\n",
    "\n",
    "\n",
    "\\begin{equation}\n",
    "\\mathbf{R}_{n \\times n} =\n",
    "\\begin{bmatrix}\n",
    "0 & 1 & 2 & \\cdots & n-1 \\\\\n",
    "& 0 & 1 & \\cdots & n-2 \\\\\n",
    "&   &\\ddots &\\ddots & \\vdots \\\\\n",
    "&   &   & \\ddots & 1 \\\\\n",
    "&   &   &        & 0\n",
    "\\end{bmatrix}\n",
    "\\end{equation}\n",
    "\n",
    "The rank-differential matrix $\\mathbf{R} \\in \\mathbb{R}^{n \\times n}$ is an upper-triangular matrix and its $ij$-th element specifies the difference in ranking between team $i$ and team $j$. Considering the rank-differential matrix in **Fig. (ii)** as the target matrix $\\mathbf{B}$, the two-sided permutation Procrustes finds the single permutation matrix that maximizes the similarity between the score-differential matrix $\\mathbf{A}$ and the rank-differential matrix $\\mathbf{B}$. This results to $[5,2,4,3,1]$ as the final rankings of the teams in **Fig. (iii)**.\n",
    "\n",
    "![Fig. 1 Ranking by reordering with two-sided permutation with one-transformation](notebook_data/ranking_reordering/ranking.png \"Fig. 1 Ranking by reordering with two-sided permutation with one-transformation\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Ranks =  [5 2 4 3 1]\n"
     ]
    }
   ],
   "source": [
    "# ranking by reordering with 2-sided permutation procrustes (with single transformation)\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "from procrustes import permutation_2sided\n",
    "\n",
    "# input score-differential matrix\n",
    "A = np.array([[ 0, 0, 0 ,  0,  0 ],    # Duke\n",
    "              [45, 0, 18,  8,  20],    # Miami\n",
    "              [ 3, 0, 0 ,  2,  0 ],    # UNC\n",
    "              [31, 0, 0 ,  0,  0 ],    # UVA\n",
    "              [45, 0, 27, 38,  0 ]])   # VT\n",
    "\n",
    "# make rank-differential matrix\n",
    "n = A.shape[0]\n",
    "B = np.zeros((n, n))\n",
    "for index in range(n):\n",
    "    B[index, index:] = range(0, n - index)\n",
    "\n",
    "# rank teams using two-sided Procrustes\n",
    "result = permutation_2sided(A, B, single=True, method=\"approx-normal1\")\n",
    "\n",
    "# compute teams' ranks (by adding 1 because Python's list index starts from 0)\n",
    "_, ranks = np.where(result.t == 1)\n",
    "ranks += 1\n",
    "print(\"Ranks = \", ranks)     # displays [5, 2, 4, 3, 1]"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.12"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}