Learning Mixed Membership Community Models in Social Tagging Networks through Tensor Methods

2015/03/16 by Anandkumar, Anima, Sedghi, Hanie
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Social and Information Networks (cs.SI)

paper · doi:10.48550/arxiv.1503.04567

Abstract

Community detection in graphs has been extensively studied both in theory and in applications. However, detecting communities in hypergraphs is more challenging. In this paper, we propose a tensor decomposition approach for guaranteed learning of communities in a special class of hypergraphs modeling social tagging systems or folksonomies. A folksonomy is a tripartite 3-uniform hypergraph consisting of (user, tag, resource) hyperedges. We posit a probabilistic mixed membership community model, and prove that the tensor method consistently learns the communities under efficient sample complexity and separation requirements.

Related

• Community Detection for Hypergraph Networks via Regularized Tensor Power Iteration
• A Tensor Approach to Learning Mixed Membership Community Models
• From Node Embedding To Community Embedding : A Hyperbolic Approach
• Community Detection in Hypergraphs, Spiked Tensor Models, and Sum-of-Squares
• Community Detection in General Hypergraph via Graph Embedding