Pairwise comparisons in spectral ranking

This paper addresses the problem of pairwise comparisons in spectral ranking from an ordinary differential equation view. Given a nonnegative symmetric matrix A of order n, we provide an O(1) algorithm for single pairwise comparison without computing the exact value of the principal eigenvector of A if assuming A and A2 have been constructed offline, which further leads to an O(ν2) algorithm for ranking any subset of size ν, or an O(kn) algorithm for the top k selection. We prove that in ER graphs the correct rate of pairwise comparisons converges to one as n approaches infinity. We also experimentally demonstrate the high correct rate on various artificial and real-world graphs.