Analysis of crowdsourced sampling strategies for HodgeRank with sparse random graphs

作者：Osting, Braxton^*; Xiong, Jiechao; Xu, Qianqian; Yao, Yuan^*

来源：Applied and Computational Harmonic Analysis, 2016, 41(2): 540-560.

DOI：10.1016/j.acha.2016.03.007

• Crowdsourcing
• Paired comparison
• Algebraic connectivity
• Erdos-Renyi random graph

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.

• 出版日期2016-9
• 单位北京大学; 中国科学院信息工程研究所