Consistent Estimation of Mixed Memberships with Successive Projections
arXiv:1707.01350 · doi:10.1007/978-3-319-72150-7_5
Abstract
This paper considers the parameter estimation problem in Mixed Membership Stochastic Block Model (MMSB), which is a quite general instance of random graph model allowing for overlapping community structure. We present the new algorithm successive projection overlapping clustering (SPOC) which combines the ideas of spectral clustering and geometric approach for separable non-negative matrix factorization. The proposed algorithm is provably consistent under MMSB with general conditions on the parameters of the model. SPOC is also shown to perform well experimentally in comparison to other algorithms.
References in corpus (12)
- Community structure in social and biological networks
- DeepWalk: Online Learning of Social Representations
- Uncovering the overlapping community structure of complex networks in nature and society
- Mixed membership stochastic blockmodels
- Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
- Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization
- Detecting Overlapping Communities in Networks Using Spectral Methods
- Anchor-Free Correlated Topic Modeling: Identifiability and Algorithm
- Ellipsoidal Rounding for Nonnegative Matrix Factorization Under Noisy Separability
- Recovery Guarantee of Non-negative Matrix Factorization via Alternating Updates
- Consistent Estimation of Mixed Memberships with Successive Projections
- Robustness Analysis of Preconditioned Successive Projection Algorithm for General Form of Separable NMF Problem
Cited by in corpus (7)
- Mixed Membership Estimation for Social Networks
- Consistent Estimation of Mixed Memberships with Successive Projections
- Estimating Mixed Memberships with Sharp Eigenvector Deviations
- Probabilistic Simplex Component Analysis
- Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach
- Mixed Membership Graph Clustering via Systematic Edge Query
- A useful criterion on studying consistent estimation in community detection