A General Pairwise Comparison Model for Extremely Sparse Networks

Abstract

Statistical estimation using pairwise comparison data is an effective approach to analyzing large-scale sparse networks. In this article, we propose a general framework to model the mutual interactions in a network, which enjoys ample flexibility in terms of model parameterization. Under this setup, we show that the maximum likelihood estimator for the latent score vector of the subjects is uniformly consistent under a near-minimal condition on network sparsity. This condition is sharp in terms of the leading order asymptotics describing the sparsity. Our analysis uses a novel chaining technique and illustrates an important connection between graph topology and model consistency. Our results guarantee that the maximum likelihood estimator is justified for estimation in large-scale pairwise comparison networks where data are asymptotically deficient. Simulation studies are provided in support of our theoretical findings. Supplementary materials for this article are available online.

KEYWORDS:

• Entry-wise error
• Graph topology
• Maximum likelihood estimation
• Sparsity
• Uniform consistency

Supplementary Materials

Detailed proofs of Theorems 1–4, Lemma 1 and Proposition 2.

Acknowledgments

The authors are very grateful to the Editor Prof. McKeague, the Associate Editor, and two anonymous referees for their very helpful comments which significantly improved the presentation of the article. The authors also thank Prof. Tom Alberts for going through an early version of the draft, Prof. Fan R. K. Chung for explaining a proposed graph condition in the manuscript and Prof. Zhigang Bao for helpful discussion.

Notes

1 The dataset can be found at www.tennis-data.co.uk.

Additional information

Funding

Ruijian Han’s research is partially supported by the Hong Kong Research Grants Council (grant no. 14301821) and Direct Grants for Research, The Chinese University of Hong Kong. Kani Chen’s research is partially supported by the Hong Kong Research Grants Council (grant no. 16302881).