B1124
Title: Optimal network community inference under severe degree heterogeneity
Authors: Jingming Wang - Harvard University (United States) [presenting]
Tracy Ke - Harvard University (United States)
Abstract: The estimation of mixed memberships is a problem of great interest in the analysis of large social network data. A symmetric network with $n$ nodes and $K$ communities is considered, where each node $i$ has a mixed membership vector $\pi_i$ (a $K$-dimensional probability mass function). It is of great interest to reveal the optimal error rates for estimating the membership vectors. The degree corrected mixed membership (DCMM) model is adopted, and two loss metrics are considered, an unweighted $l^1$-loss and a degree-weighted $l^1$-loss. The minimax rates for both loss metrics are obtained under a very broad setting that allows for a wide range of network sparsity, severe degree heterogeneity, weak signals, and diverging $K$. A spectral algorithm is also proposed, which achieves the minimax rates for both metrics, up to some logarithmic factors. Technically, a lot of effort is required in the study of a sharp entry-wise large deviation bound for the leading eigenvectors of the regularized graph Laplacian. This result plays a key role in motivating and understanding the rate-optimal spectral algorithm.
