The DOI matches its Crossref record; 52 of the 52 references it cites were found in a registry or an index.
Statistical ranking and combinatorial Hodge theory
Open accessAbstract
We propose a technique that we call HodgeRank for ranking data that may be incomplete and imbalanced, characteristics common in modern datasets coming from e-commerce and internet applications. We are primarily interested in cardinal data based on scores or ratings though our methods also give specific insights on ordinal data. From raw ranking data, we construct pairwise rankings, represented as edge flows on an appropriate graph. Our statistical ranking method exploits the graph Helmholtzian, which is the graph theoretic analogue of the Helmholtz operator or vector Laplacian, in much the same way the graph Laplacian is an analogue of the Laplace operator or scalar Laplacian. We shall study the graph Helmholtzian using combinatorial Hodge theory, which provides a way to unravel ranking information from edge flows. In particular, we show that every edge flow representing pairwise ranking can be resolved into two orthogonal components, a gradient flow that represents the l 2-optimal global ranking and a divergence-free flow (cyclic) that measures the validity of the global ranking obtained—if this is large, then it indicates that the data does not have a good global ranking. This divergence-free flow can be further decomposed orthogonally into a curl flow (locally cyclic) and a harmonic flow (locally acyclic but globally cyclic); these provides information on whether inconsistency in the ranking data arises locally or globally. When applied to statistical ranking problems, Hodge decomposition sheds light on whether a given dataset may be globally ranked in a meaningful way or if the data is inherently inconsistent and thus could not have any reasonable global ranking; in the latter case it provides information on the nature of the inconsistencies. An obvious advantage over the NP-hardness of Kemeny optimization is that HodgeRank may be easily computed via a linear least squares regression. We also discuss connections with well-known ordinal ranking techniques such as Kemeny optimization and Borda count from social choice theory.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The magical number seven, plus or minus two: Some limits on our capacity for processing information.
Miller, G. A. (1956) · Psychological Review · doi:10.1037/h0043158 · Cited by 17,812
The magical number seven, plus or minus two: Some limits on our capacity for processing information.
Miller, G. A. (1994) · Psychological Review · doi:10.1037/0033-295x.101.2.343 · Cited by 17,161
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004
A scaling method for priorities in hierarchical structures
Saaty, T. L. (1977) · Journal of Mathematical Psychology · doi:10.1016/0022-2496(77)90033-5 · Cited by 10,360
Authoritative sources in a hyperlinked environment
Kleinberg, J. M. (1999) · Journal of the ACM · doi:10.1145/324133.324140 · Cited by 8,959
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524
LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
Paige, C. C., & Saunders, M. A. (1982) · ACM Transactions on Mathematical Software · doi:10.1145/355984.355989 · Cited by 4,387
Moran, P. A. P., & Kendall, M. G. (1951) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2980903 · Cited by 2,573
Rank Analysis of Incomplete Block Designs: I. The Method of Paired Comparisons
Bradley, R. A., & Terry, M. E. (1952) · Biometrika · doi:10.2307/2334029 · Cited by 2,412
A Difficulty in the Concept of Social Welfare
Arrow, K. J. (1950) · Journal of Political Economy · doi:10.1086/256963 · Cited by 2,079
Rank aggregation methods for the Web
Dwork, C., Kumar, R., Naor, M., & Sivakumar, D. (2001) · Proceedings of the 10th international conference on World Wide Web · doi:10.1145/371920.372165 · Cited by 1,793
RANK ANALYSIS OF INCOMPLETE BLOCK DESIGNS: THE METHOD OF PAIRED COMPARISONS
BRADLEY, R. A., & TERRY, M. E. (1952) · Biometrika · doi:10.1093/biomet/39.3-4.324 · Cited by 1,434
Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix
Condorcet, N. D. (2014) · Cambridge University Press eBooks · doi:10.1017/cbo9781139923972 · Cited by 1,417
Classification by pairwise coupling
Hastie, T., & Tibshirani, R. (1998) · The Annals of Statistics · doi:10.1214/aos/1028144844 · Cited by 1,299
The Method of Paired Comparisons.
Curnow, R. N., & David, H. A. (1964) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2344014 · Cited by 1,271
Mathematics without Numbers: Towards a Modal-Structural Interpretation
Hellman, G. (1993) · doi:10.1093/0198240341.001.0001 · Cited by 1,158
Govindarajulu, Z., Kendall, M., & Gibbons, J. D. (1992) · Technometrics · doi:10.2307/1269571 · Cited by 1,130
Can Investors Profit from the Prophets? Security Analyst Recommendations and Stock Returns
Barber, B., Lehavy, R., McNichols, M., & Trueman, B. (2001) · The Journal of Finance · doi:10.1111/0022-1082.00336 · Cited by 1,099
Large Margin Rank Boundaries for Ordinal Regression
Herbrich, R., Graepel, T., & Obermayer, K. (2000) · Advances in Large-Margin Classifiers · doi:10.7551/mitpress/1113.003.0010 · Cited by 1,074
Interior Point Algorithms: Theory and Analysis
Ye, Y. (1997) · Wiley eBooks · doi:10.1002/9781118032701 · Cited by 939
Self-citationMémoire sur les élections au scrutin
Daunou, P. C. F. (1803) · Medical Entomology and Zoology · Cited by 824
The Possibility of Social Choice
Sen, A. (1999) · American Economic Review · doi:10.1257/aer.89.3.349 · Cited by 763
Young, H. P. (1988) · American Political Science Review · doi:10.2307/1961757 · Cited by 746
BRADLEY, R. A. (1954) · Biometrika · doi:10.1093/biomet/41.3-4.502 · Cited by 716
Aggregating inconsistent information
Ailon, N., Charikar, M., & Newman, A. (2008) · Journal of the ACM · doi:10.1145/1411509.1411513 · Cited by 630
ON THE METHOD OF PAIRED COMPARISONS
Kendall, M. G., & Smith, B. B. (1940) · Biometrika · doi:10.1093/biomet/31.3-4.324 · Cited by 557
Scalable Collaborative Filtering with Jointly Derived Neighborhood Interpolation Weights
Bell, R. M., & Koren, Y. (2007) · Seventh IEEE International Conference on Data Mining (ICDM 2007) · doi:10.1109/icdm.2007.90 · Cited by 499
Inconsistency and rank preservation
Saaty, T. L., & Vargas, L. G. (1984) · Journal of Mathematical Psychology · doi:10.1016/0022-2496(84)90027-0 · Cited by 474
The method of paired comparisons for social values.
Thurstone, L. L. (1927) · The Journal of Abnormal and Social Psychology · doi:10.1037/h0065439 · Cited by 467
A Consistent Extension of Condorcet’s Election Principle
Young, H. P., & Levenglick, A. (1978) · SIAM Journal on Applied Mathematics · doi:10.1137/0135023 · Cited by 455
SPECTRAL GRAPH THEORY (CBMS Regional Conference Series in Mathematics 92)
Biggs, N. (1998) · Bulletin of the London Mathematical Society · doi:10.1112/s0024609397223611 · Cited by 433
(2000) · CrossRef Listing of Deleted DOIs · doi:10.1162/1532443041827916 · Cited by 363
Mosteller, F. (1951) · Psychometrika · doi:10.1007/bf02313422 · Cited by 343
Rank Correlation Methods (5th ed.).
Marden, J. I., Kendall, M., & Gibbons, J. D. (1992) · Journal of the American Statistical Association · doi:10.2307/2290477 · Cited by 342
Mosteller, F. (2007) · Springer Series in Statistics · doi:10.1007/978-0-387-44956-2_10 · Cited by 239
Mathematical models in the social sciences
Snell, J. L., & Kemeny, J. G. (1972) · Cited by 222
Can Investors Profit from the Prophets? Consensus Analyst Recommendations and Stock Returns
Barber, B. M., Lehavy, R., McNichols, M. F., & Trueman, B. (1998) · doi:10.2139/ssrn.137400 · Cited by 220
Methodologies and Algorithms for Group-Rankings Decision
Hochbaum, D. S., & Levin, A. (2006) · Management Science · doi:10.1287/mnsc.1060.0540 · Cited by 213
Aggregating inconsistent information
Ailon, N., Charikar, M., & Newman, A. (2005) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1060590.1060692 · Cited by 187
Topology of random clique complexes
Kahle, M. (2009) · Discrete Mathematics · doi:10.1016/j.disc.2008.02.037 · Cited by 182
The Minimum Sum of Absolute Errors Regression: A State of the Art Survey
Narula, S. C., & Wellington, J. F. (1982) · International Statistical Review / Revue Internationale de Statistique · doi:10.2307/1402501 · Cited by 165
Magnitude-preserving ranking algorithms
Cortes, C., Mohri, M., & Rastogi, A. K. (2007) · International Conference on Machine Learning · doi:10.1145/1273496.1273518 · Cited by 119
Distributed Coverage Verification in Sensor Networks Without Location Information
Tahbaz-Salehi, A., & Jadbabaie, A. (2010) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2010.2047541 · Cited by 117
MINRES-QLP: A Krylov Subspace Method for Indefinite or Singular Symmetric Systems
Choi, S.-C. T., Paige, C. C., & Saunders, M. A. (2011) · SIAM Journal on Scientific Computing · doi:10.1137/100787921 · Cited by 114
The Method of Paired Comparisons (2nd ed.).
Rossman, A. J., & David, H. A. (1989) · Journal of the American Statistical Association · doi:10.2307/2289964 · Cited by 105
A geometric examination of Kemeny's rule
Saari, D. G., & Merlin, V. R. (2000) · Social Choice and Welfare · doi:10.1007/s003550050171 · Cited by 104
Computing Betti Numbers via Combinatorial Laplacians
Friedman, J. (1998) · Algorithmica · doi:10.1007/pl00009218 · Cited by 102
Convex Rank Tests and Semigraphoids
Morton, J., Pachter, L. S., Shiu, A., Sturmfels, B., & Wienand, O. (2009) · SIAM Journal on Discrete Mathematics · doi:10.1137/080715822 · Cited by 71
Bartholdi, L., Schick, T., Smale, N., & Smale, S. (2011) · Foundations of Computational Mathematics · doi:10.1007/s10208-011-9107-3 · Cited by 26
Remarks about a Paired Comparison Model
Noether, G. E. (1960) · Psychometrika · doi:10.1007/bf02289753 · Cited by 23
Distributed coverage verification in sensor networks without location information
Tahbaz-Salehi, A., & Jadbabaie, A. (2008) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2008.4738751 · Cited by 23
Zhang, J. (2004) · Journal of Mathematical Psychology · doi:10.1016/j.jmp.2003.12.002 · Cited by 17
Cited by
Massive Online Crowdsourced Study of Subjective and Objective Picture Quality
Ghadiyaram, D., & Bovik, A. C. (2016) · IEEE Transactions on Image Processing · doi:10.1109/tip.2015.2500021 · Cited by 782
From networks to optimal higher-order models of complex systems
Lambiotte, R., Rosvall, M., & Scholtes, I. (2019) · Nature Physics · doi:10.1038/s41567-019-0459-y · Cited by 483
Fine-Grained Visual Comparisons with Local Learning
Yu, A., & Grauman, K. (2014) · 2014 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2014.32 · Cited by 454
What are higher-order networks?
Bick, C., Gross, E., Harrington, H. A., & Schaub, M. T. (2023) · SIAM Review · doi:10.1137/21m1414024 · Cited by 420
Crowdsourced Data Management: A Survey
Li, G., Wang, J., Zheng, Y., & Franklin, M. J. (2016) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2016.2535242 · Cited by 283
Metadata
- Authors
- Jiang, X., Lim, L.-H., Yao, Y., & Ye, Y.
- Venue
- Mathematical Programming
- Published
- 2010-11-28
- Volume
- 127
- Issue
- 1
- Pages
- 203-244
- ISSN
- 0025-5610 (ISSN-L)
- 1436-4646
- OpenAlex
- W2130406232
- Cited by
- 335
- References
- 52
- FWCI
- 35.86
- Type
- journal article
- Language
- en
- Open access
- hybrid
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.