A Tensor Approach to Learning Mixed Membership Community Models

Abstract

Community detection is the task of detecting hidden communities from observed interactions. Guaranteed community detection has so far been mostly limited to models with non-overlapping communities such as the stochastic block model. In this paper, we remove this restriction, and provide guaranteed community detection for a family of probabilistic network models with overlapping communities, termed as the mixed membership Dirichlet model, first introduced by Airoldi et al. This model allows for nodes to have fractional memberships in multiple communities and assumes that the community memberships are drawn from a Dirichlet distribution. Moreover, it contains the stochastic block model as a special case. We propose a unified approach to learning these models via a tensor spectral decomposition method. Our estimator is based on low-order moment tensor of the observed network, consisting of 3-star counts. Our learning method is fast and is based on simple linear algebraic operations, e.g. singular value decomposition and tensor power iterations. We provide guaranteed recovery of community memberships and model parameters and present a careful finite sample analysis of our learning method. As an important special case, our results match the best known scaling requirements for the (homogeneous) stochastic block model.

References in corpus (6)

• Uncovering the overlapping community structure of complex networks in nature and society
• A Spectral Algorithm for Latent Dirichlet Allocation
• Stochastic Block Models and Reconstruction
• Breaking the Small Cluster Barrier of Graph Clustering
• Dirichlet draws are sparse with high probability
• Statistical Algorithms and a Lower Bound for Detecting Planted Clique

Cited by in corpus (16)

• Rate-optimal graphon estimation
• A goodness-of-fit test for stochastic block models
• A statistical model for tensor PCA
• Tensor Decompositions for Identifying Directed Graph Topologies and Tracking Dynamic Networks
• Community Detection with Side Information: Exact Recovery under the Stochastic Block Model
• Tensors, Learning, and 'Kolmogorov Extension' for Finite-alphabet Random Vectors
• Multilayer Network Science: from Cells to Societies
• Identification of Overlapping Communities via Constrained Egonet Tensor Decomposition
• A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models
• Mixed Membership Graph Clustering via Systematic Edge Query
• A useful criterion on studying consistent estimation in community detection
• Partially Observed Dynamic Tensor Response Regression
• Lower bounds on the rank and symmetric rank of real tensors
• Side Information in the Binary Stochastic Block Model: Exact Recovery
• Active Algorithms For Preference Learning Problems with Multiple Populations
• Efficient coordinate-descent for orthogonal matrices through Givens rotations