Rank Centrality: Ranking from Pairwise Comparisons

References

• Adler M, Gemmell P, Harchol-Balter M, Karp RM, Kenyon C (1994) Selection in the presence of noise: The design of playoff systems. Proc. 5th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’94 (SIAM, Philadelphia), 564–572.Google Scholar
• Ailon N (2010) Aggregation of partial rankings, p-ratings and top-m lists. Algorithmica 57(2):284–300.Crossref, Google Scholar
• Ailon N, Charikar M, Newman A (2008) Aggregating inconsistent information: Ranking and clustering. J. ACM (JACM) 55(5):23.Crossref, Google Scholar
• Altman A, Tennenholtz M (2005) Ranking systems: The pagerank axioms. Riedl J, Kearns MJ, Reiter MK, eds. Proc. 6th ACM Conf. Electronic Commerce, EC ’05 (ACM, New York), 1–8.Crossref, Google Scholar
• Ammar A, Shah D (2011) Ranking: Compare, don’t score. 49th Annual Allerton Conf. Comm., Control, and Comput., Allerton ’11 (IEEE, Piscataway, NJ), 776–783.Crossref, Google Scholar
• Arrow KJ (1963) Social Choice and Individual Values (Yale University Press, New Haven, CT).Google Scholar
• Boyd S, Ghosh A, Prabhakar B, Shah D (2005) Mixing times for random walks on geometric random graphs. Demetrescu C, Sedgewick R, Tamassia R, eds. Proc. Second Workshop Analytic Algorithms Combinatorics, ANALCO ’05 (SIAM, Philadelphia), 240–249.Google Scholar
• Bradley RA, Terry ME (1955) Rank analysis of incomplete block designs: I. The method of paired comparisons. Biometrika 39(3/4):324–345.Crossref, Google Scholar
• Braverman M, Mossel E (2008) Noisy sorting without resampling. Teng S-H, ed. Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’08 (SIAM, Philadelphia), 268–276.Google Scholar
• Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine. Seventh Internat. World-Wide Web Conf., WWW7 (Elsevier, Amsterdam), 107–117.Crossref, Google Scholar
• Candès EJ, Recht B (2009) Exact matrix completion via convex optimization. Foundations of Computational Math. 9(6):717–772.Crossref, Google Scholar
• Condorcet M (1785) Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix (l’Imprimerie Royale, Paris).Google Scholar
• David HA (1963) The Method of Paired Comparisons (Charles Griffin and Company, London).Google Scholar
• de Borda J-C (1781) Mémoire sur les élections au scrutin. Mémoires de l’Académie royale des sciences, 657–664.Google Scholar
• Diaconis P, Saloff-Coste L (1993) Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3(3):696–730.Crossref, Google Scholar
• Duchi JC, Mackey L, Jordan MI (2010) On the consistency of ranking algorithms. Fürnkranz J, Joachims T, eds. Proc. 27th Internat. Conf. Machine Learning, ICML ’10 (Omnipress, Madison, WI), 327–334.Google Scholar
• Dwork C, Kumar R, Naor M, Sivakumar D (2001) Rank aggregation methods for the web. Shen VY, Saito N, Lyu MR, Zurko ME, eds. Proc. 10th Internat. World Wide Web Conf., WWW ’10 (ACM, New York), 613–622.Crossref, Google Scholar
• Dwork C, Kumar R, Naor M, Sivakumar D (2001b) Rank aggregation methods for the web. Proc. 10th Internat. World Wide Web Conf. (ACM, New York), 613–622.Crossref, Google Scholar
• Farnoud F, Touri B, Milenkovic O (2012) Novel distance measures for vote aggregation. Preprint, arXiv:1203.6371.Google Scholar
• Ford Jr LR (1957) Solution of a ranking problem from binary comparisons. Amer. Math. Monthly 64(8):28–33.Crossref, Google Scholar
• Gleich DF, Lim L (2011) Rank aggregation via nuclear norm minimization. Apté C, Ghosh J, Smyth P, eds. Proc. 17th ACM SIGKDD Internat. Conf. Knowledge Discovery and Data Mining (ACM, New York), 60–68.Crossref, Google Scholar
• Guiver J, Snelson E (2009) Bayesian inference for Plackett-Luce ranking models. Pohoreckyj Danyluk A, Bottou L, Littman ML, eds. Proc. 26th Annual Internat. Conf. Machine Learn., ICML ’09 (ACM, New York), 377–384. [Available at http://sites.stat.psu.edu/∼dhunter/code/btmatlab/.] Crossref, Google Scholar
• Hajek B, Oh S, Xu J (2014) Minimax-optimal inference from partial rankings. Ghahramani Z, Welling M, Cortes C, Lawrence ND, Weinberger KQ, eds. Adv. Neural Inform. Processing Systems (NIPS), 1475–1483.Google Scholar
• Hochbaum DS (2006) Ranking sports teams and the inverse equal paths problem. Spirakis P, Mavronicolas M, Kontogiannis S, eds. Internet and Network Economics (Springer, Berlin), 307–318.Crossref, Google Scholar
• Horn RA, Johnson CR (1985) Matrix Analysis (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Hunter DR (2004) MM algorithms for generalized Bradley-Terry models. Ann. Statist. 32(1):384–406.Crossref, Google Scholar
• Jiang X, Lim L, Yao Y, Ye Y (2011) Statistical ranking and combinatorial Hodge theory. Math. Programming 127(1):203–244.Crossref, Google Scholar
• Kamvar SD, Schlosser MT, Garcia-Molina H (2003) The eigentrust algorithm for reputation management in P2P networks. Hencsey G, White B, Chen Y-F, Kovács L, Lawrence S, eds. Proc. 12th Internat. Conf. World Wide Web, WWW ’03 (ACM, New York), 640–651.Crossref, Google Scholar
• Keener JP (1993) The Perron-Frobenius theorem and the ranking of football teams. SIAM Rev. 35(1):80–93.Crossref, Google Scholar
• Kendall MG (1955) Further contributions to the theory of paired comparisons. Biometrics 11(1):43–62.Crossref, Google Scholar
• Kendall MG, Smith BB (1940) On the method of paired comparisons. Biometrika 31(3):324–345.Crossref, Google Scholar
• Keshavan RH, Montanari A, Oh S (2010) Matrix completion from noisy entries. J. Machine Learn. Res. 11(1):2057–2078.Google Scholar
• Lu T, Boutilier C (2011) Learning Mallows models with pairwise preferences. Proc. 28th Internat. Conf. Machine Learn. ICML ’11 (Omnipress, Madison, WI), 145–152.Google Scholar
• Luce DR (1959) Individual Choice Behavior (John Wiley & Sons, New York).Google Scholar
• Mallows CL (1957) Non-null ranking models. I. Biometrika 44(1): 114–130.Crossref, Google Scholar
• McFadden D (1973) Conditional logit analysis of qualitative choice behavior. Frontiers Econometrics 1(1):105–142.Google Scholar
• Mosteller F (1951) Remarks on the method of paired comparisons: I. The least squares solution assuming equal standard deviations and equal correlations. Psychometrika 16(1):3–9.Crossref, Google Scholar
• Negahban S, Wainwright MJ (2012) Restricted strong convexity and (weighted) matrix completion: Optimal bounds with noise. J. Machine Learn. Res. 13(1):1665–1697.Google Scholar
• Newman MEJ (2010) Networks: An Introduction (Oxford University Press, Oxford, UK).Crossref, Google Scholar
• Osting B, Brune C, Osher S (2013) Enhanced statistical rankings via targeted data collection. Proc. 30th Internat. Conf. Machine Learn., ICML ’13 (JMLR.org), 489–497.Google Scholar
• Plackett RL (1975) The analysis of permutations. Appl. Statist. 24(2): 193–202.Crossref, Google Scholar
• Rajkumar A, Agarwal S (2014) A statistical convergence perspective of algorithms for rank aggregation from pairwise data. Proc. 31st Internat. Conf. Machine Learn., ICML ’14 (JMLR.org), 118–126.Google Scholar
• Rao CR (1945) Information and accuracy attainable in the estimation of statistical parameters. Bull. Calcutta Math. Soc. 37(3):81–91.Google Scholar
• Saaty TL (2003) Decision making with the AHP: Why is the principal eigenvector necessary. Eur. J. Oper. Res. 145(1):85–91.Crossref, Google Scholar
• Salganik MJ, Levy KEC (2012) Wiki surveys: Open and quantifiable social data collection. Preprint, arXiv:1202.0500.Google Scholar
• Seeley JR (1949) The net of reciprocal influence. Canadian J. Psych. 3(4):234–240.Crossref, Google Scholar
• Shah D, Zaman T (2011) Rumors in a network: Who’s the culprit? IEEE Trans. Inform. Theory 57(8):5163–5181.Crossref, Google Scholar
• Shah D, Zaman T (2016) Finding rumor sources on random trees. Oper. Res. 64(3):736–755.Link, Google Scholar
• Talluri KT, Van Ryzin G (2005) The Theory and Practice of Revenue Management (Springer, New York).Crossref, Google Scholar
• Tropp J (2012) User-friendly tail bounds for sums of random matrices. Foundations of Computational Math. 12(4):389–434.Crossref, Google Scholar
• Vigna S (2009) Spectral ranking. Preprint, arXiv: 0912.0238.Google Scholar
• Volkovs MN, Zemel RS (2012) A flexible generative model for preference aggregation. Mille A, Gandon FL, Misselis J, Rabinovich M, Staab S, eds. Proc. 21st Internat. Conf. World Wide Web, WWW ’12 (ACM, New York), 479–488.Crossref, Google Scholar
• Wei TH (1952) The algebraic foundations of ranking theory. Ph.D. thesis, University of Cambridge, Cambridge, UK.Google Scholar