Title: Estimating network memberships by simplex vertex hunting,
Abstract: Consider an undirected mixed membership network with $n$ nodes and $K$
communities. For each node $1 \leq i \leq n$, we model the membership by
$\pi_{i} = (\pi_{i}(1), \pi_{i}(2), \ldots$, $\pi_{i}(K))'$, where $\pi_{i}(k)$
is the probability that node $i$ belongs to community $k$, $1 \leq k \leq K$.
We call node $i$ "pure" if $\pi_i$ is degenerate and "mixed" otherwise. The
primary interest is to estimate $\pi_i$, $1 \leq i \leq n$.
We model the adjacency matrix $A$ with a Degree Corrected Mixed Membership
(DCMM) model. Let $\hat{\xi}_1, \hat{\xi}_2, \ldots, \hat{\xi}_K$ be the first
$K$ eigenvectors of $A$. We define a matrix $\hat{R} \in \mathbb{R}^{n, K-1}$
by $\hat{R}(i,k) = \hat{\xi}_{k+1}(i)/\hat{\xi}_1(i)$, $1 \leq k \leq K-1$, $1
\leq i \leq n$. The matrix can be viewed as a distorted version of its
non-stochastic counterpart $R \in \mathbb{R}^{n, K-1}$, which is unknown but
contains all information we need for the memberships.
We reveal an interesting insight: There is a simplex ${\cal S}$ in
$\mathbb{R}^{K-1}$ such that row $i$ of $R$ corresponds to a vertex of ${\cal
S}$ if node $i$ is pure, and corresponds to an interior point of ${\cal S}$
otherwise. Vertex Hunting (i.e., estimating the vertices of ${\cal S}$) is thus
the key to our problem.
The matrix $\hat{R}$ is a row-wise normalization on the matrix of
eigenvectors $\hat{\Xi}=[\hat{\xi}_1,\ldots,\hat{\xi}_K]$, first proposed by
Jin (2015). Alternatively, we may normalize $\hat{\Xi}$ by the row-wise
$\ell^q$-norms (e.g., Supplement of Jin (2015)), but it won't give rise to a
simplex so is less convenient.
We propose a new approach $\textit{Mixed-SCORE}$ to estimating the
memberships, at the heart of which is an easy-to-use Vertex Hunting algorithm.
The approach is successfully applied to $4$ network data sets. We also derive
the rate of convergence for Mixed-SCORE.