Rank Centrality Iterative Random-Walk Spectral Ranking from Pairwise Comparisons

An iterative spectral rank-aggregation algorithm (introduced by Sahand Negahban, Sewoong Oh, and Devavrat Shah in 2017) that estimates latent preference scores $w_1,\dots,w_n > 0$ under the Bradley–Terry–Luce (BTL) / Multinomial Logit (MNL) pairwise comparison model from $k$ comparisons per edge on a comparison graph $G = ([n], E)$. Given empirical win fractions $a_{ij} = \frac{1}{k}\sum_{l=1}^k Y_{ij}^l$ and normalized pairwise ratios $A_{ij} = a_{ij}/(a_{ij}+a_{ji})$ (or Beta$(\varepsilon,\varepsilon)$-regularized ratios $(a_{ij}+\varepsilon)/(a_{ij}+a_{ji}+2\varepsilon)$, Equation 5), Rank Centrality constructs the random-walk transition matrix $P_{ij} = \frac{1}{d_{\max}}A_{ij}$ for $(i,j)\in E$, $i\ne j$, and $P_{ii} = 1 - \frac{1}{d_{\max}}\sum_{l\ne i}A_{il}$ (Equation 1), where $d_{\max}$ is the maximum vertex degree, and computes its unique stationary distribution $\pi^T = \pi^T P$ via power iteration $p_{t+1}^T = p_t^T P$ (Equation 2). Scaling every off-diagonal transition by the uniform global maximum degree $1/d_{\max}$ (rather than local vertex degree $1/d_i$ as in Dwork et al.'s MC3) ensures that the population transition matrix $\tilde{P}_{ij} = \frac{1}{d_{\max}}\frac{w_j}{w_i+w_j}$ satisfies detailed balance $\tilde{\pi}(i)\tilde{P}_{ij} = \tilde{\pi}(j)\tilde{P}_{ji}$ with exact stationary distribution $\tilde{\pi}(i) = w_i / \sum_l w_l$ on any connected graph $G$. Using a self-adjoint $L^2(\tilde{\pi})$ perturbation inequality (Lemma 2, Equation 11), matrix Bernstein concentration $\|P - \tilde{P}\|_2 \le C\sqrt{\log n / (k d_{\max})}$ (Lemma 3), and a Dirichlet-form Markov chain comparison theorem relating $1 - \lambda_{\max}(\tilde{P}) \ge \frac{d_{\min}}{b^2 d_{\max}}\xi$ to the random-walk Laplacian spectral gap $\xi = 1 - \lambda_{\max}(D^{-1}B)$ (Lemmas 4 and 6, Equations 26–27), Theorem 1 proves $\frac{\|\pi - \tilde{\pi}\|_2}{\|\tilde{\pi}\|_2} \le \frac{C b^{5/2}\kappa}{\xi}\sqrt{\frac{\log n}{k d_{\max}}}$, matching the minimax Fano lower bound of Theorem 3 up to logarithmic factors on Erdős–Rényi graphs (Theorem 2).