Events

Dr. Jingming Wang
Postdoctoral fellow
Department of Statistics
Harvard University

Real networks often have severe degree heterogeneity, with maximum, average, and minimum node degrees differing significantly. This paper examines the impact of degree heterogeneity on statistical limits of network data analysis. Introducing the empirical heterogeneity distribution (EHD) under a degree-corrected mixed membership model, we demonstrate that the optimal rate of mixed membership estimation is directly linked to EHD. Surprisingly, severe degree heterogeneity can decelerate the error rate, even when the overall sparsity remains unchanged. To develop a spectral algorithm that is rate-optimal for arbitrary EHD, we propose the “two normalizations” approach to enhance the performance of an existing spectral algorithm, Mixed-SCORE. Our approach involves a pre-PCA normalization parameterized by b ∈ R. The crucial question is how to choose b to simultaneously optimize the signal-to-noise ratios for all entries of leading empirical eigenvectors. Remarkably, we find that universally choosing b = 1/2 yields favorable results. The resulting algorithm is rate-optimal for networks with arbitrary degree heterogeneity. Our findings have two significant implications: (1) Degree heterogeneity indeed influences the fundamental statistical limits; and (2) Achieving optimal adaptivity to degree heterogeneity is possible, provided that the algorithm is thoughtfully designed.