CONSISTENT NONPARAMETRIC ESTIMATION FOR HEAVY-TAILED SPARSE GRAPHS

• 成果类型: Article
• 署名作者: Borgs, Christian; Chayes, Jennifer T.; Cohn, Henry; Ganguly, Shirshendu
• 署名单位: University of California System; University of California Berkeley; Microsoft
• 刊物名称: ANNALS OF STATISTICS
• ISSN/ISSBN: 0090-5364
• DOI: 10.1214/20-AOS1985
• 发表日期: 2021
• 页码: 1904-1930
• 关键词: l-p theory; stochastic blockmodels; convergent sequences; network models; RECOVERY; frequencies; algorithm; LIMITS

摘要

We study graphons as a nonparametric generalization of stochastic block models, and show how to obtain compactly represented estimators for sparse networks in this framework. In contrast to previous work, we relax the usual boundedness assumption for the generating graphon and instead assume only integrability, so that we can handle networks that have long tails in their degree distributions. We also relax the usual assumption that the graphon is defined on the unit interval, to allow latent position graphs based on more general spaces. We analyze three algorithms. The first is a least squares algorithm, which gives a consistent estimator for all square-integrable graphons, with errors expressed in terms of the best possible stochastic block model approximation. Next, we analyze an algorithm based on the cut norm, which works for all integrable graphons. Finally, we show that clustering based on degrees works whenever the underlying degree distribution is atomless.