A Tensor Approach to Learning Mixed Membership Community Models

摘要

Community detection is the task of detecting hidden communitiesfrom observed interactions. Guaranteed community detection hasso far been mostly limited to models with non-overlappingcommunities such as the stochastic block model. In this paper,we remove this restriction, and provide guaranteed communitydetection for a family of probabilistic network models withoverlapping communities, termed as the mixed membershipDirichlet model, first introduced by Airoldi et al. (2008). Thismodel allows for nodes to have fractional memberships inmultiple communities and assumes that the community membershipsare drawn from a Dirichlet distribution. Moreover, it containsthe stochastic block model as a special case. We propose aunified approach to learning these models via a tensor spectraldecomposition method. Our estimator is based on low-order momenttensor of the observed network, consisting of $3$-star counts.Our learning method is fast and is based on simple linearalgebraic operations, e.g., singular value decomposition andtensor power iterations. We provide guaranteed recovery ofcommunity memberships and model parameters and present a carefulfinite sample analysis of our learning method. As an importantspecial case, our results match the best known scalingrequirements for the (homogeneous) stochastic block model. color="gray">