A Sharp Lower Bound for Mixed-membership Estimation

Understand

Consider an undirected network with $n$ nodes and $K$ perceivable communities, where some nodes may have mixed memberships.

• We assume that for each node $1 \leq i \leq n$, there is a probability mass function $\pi_i$ defined over $\{1, 2, \ldots, K\}$ such that \[ \pi_i(k) = \mbox{the weight of node $i$ on community $k$}, \qquad 1 \leq k \leq K.
• \] The goal is to estimate $\{\pi_i, 1 \leq i \leq n\}$ (i.e., membership estimation).
• We model the network with the {\it degree-corrected mixed membership (DCMM)} model \cite{Mixed-SCORE}.