| Title | Analysis of crowdsourced sampling strategies for HodgeRank with sparse random graphs |
| Authors | Osting, Braxton Xiong, Jiechao Xu, Qianqian Yao, Yuan |
| Affiliation | Univ Utah, Dept Math, Salt Lake City, UT 84112 USA. Chinese Acad Sci, Inst Informat Engn, Beijing 100093, Peoples R China. Peking Univ, BICMR, Beijing 100871, Peoples R China. Peking Univ, Sch Math Sci, BICMR LMAM LMEQF LMP, Beijing 100871, Peoples R China. Univ Utah, Dept Math, Salt Lake City, UT 84112 USA. Yao, Y (reprint author), Peking Univ, Sch Math Sci, BICMR LMAM LMEQF LMP, Beijing 100871, Peoples R China. |
| Keywords | Crowdsourcing Paired comparison Algebraic connectivity Erdos-Renyi random graph IMAGE RETRIEVAL RANKING FLOWS |
| Issue Date | 2016 |
| Publisher | 5th Tri-Annual International Conference on Computational Harmonic Analysis (ICCHA) |
| Citation | 5th Tri-Annual International Conference on Computational Harmonic Analysis (ICCHA).2016,41(2),540-560. |
| Abstract | Crowdsourcing platforms are now extensively used for conducting subjective pairwise comparison studies. In this setting, a pairwise comparison dataset is typically gathered via random sampling, either with or without replacement. In this paper, we use tools from random graph theory to analyze these two random sampling methods for the HodgeRank estimator. Using the Fiedler value of the graph as a measurement for estimator stability (informativeness), we provide a new estimate of the Fiedler value for these two random graph models. In the asymptotic limit as the number of vertices tends to infinity, we prove the validity of the estimate. Based on our findings, for a small number of items to be compared, we recommend a two-stage sampling strategy where a greedy sampling method is used initially and random sampling without replacement is used in the second stage. When a large number of items is to be compared, we recommend random sampling with replacement as this is computationally inexpensive and trivially parallelizable. Experiments on synthetic and real-world datasets support our analysis. (C) 2016 Elsevier Inc. All rights reserved. |
| URI | http://hdl.handle.net/20.500.11897/458922 |
| ISSN | 1063-5203 |
| DOI | 10.1016/j.acha.2016.03.007 |
| Indexed | SCI(E) |
| Appears in Collections: | 北京国际数学研究中心 数学科学学院 数学及其应用教育部重点实验室 |
