Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing

作     者：Gao, Chao Ma, Zongming 

作者机构：Univ Chicago Dept Stat 5747 S Ellis AveJones 314 Chicago IL 60637 USA Univ Penn Dept Stat 3730 Walnut St Philadelphia PA 19104 USA 

出 版 物：《STATISTICAL SCIENCE》 (统计科学)

年 卷 期：2021年第36卷第1期

页      面：16-33页

核心收录：

学科分类：0202[经济学-应用经济学] 02[经济学] 020208[经济学-统计学] 07[理学] 0714[理学-统计学（可授理学、经济学学位）] 

基　　金：NSF [DMS-1712957] NSF CAREER Award [DMS-1847590, DMS-1352060] Sloan Research Fellowship 

主　　题：Clustering Minimax rates polynomial-time algorithms random graphs social networks 

摘      要：This paper surveys some recent developments in fundamental limits and optimal algorithms for network analysis. We focus on minimax optimal rates in three fundamental problems of network analysis: graphon estimation, community detection and hypothesis testing. For each problem, we review state-of-the-art results in the literature followed by general principles behind the optimal procedures that lead to minimax estimation and testing. This allows us to connect problems in network analysis to other statistical inference problems from a general perspective.