Optimal Network Membership Estimation Under Severe Degree Heterogeneity
share
Real networks often have severe degree heterogeneity. We are interested in studying the effect of degree heterogeneity on estimation of the underlying community structure. We consider the degree-corrected mixed membership model (DCMM) for a symmetric network with n nodes and K communities, where each node i has a degree parameter θ_i and a mixed membership vector π_i. The level of degree heterogeneity is captured by F_n(·) – the empirical distribution associated with n (scaled) degree parameters. We first show that the optimal rate of convergence for the ℓ^1-loss of estimating π_i's depends on an integral with respect to F_n(·). We call a method optimally adaptive to degree heterogeneity (in short, optimally adaptive) if it attains the optimal rate for arbitrary F_n(·). Unfortunately, none of the existing methods satisfy this requirement. We propose a new spectral method that is optimally adaptive, the core idea behind which is using a pre-PCA normalization to yield the optimal signal-to-noise ratio simultaneously at all entries of each leading empirical eigenvector. As one technical contribution, we derive a new row-wise large-deviation bound for eigenvectors of the regularized graph Laplacian.
READ FULL TEXT