CaltechAUTHORS
  A Caltech Library Service

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

Anandkumar, Anima and Sedghi, Hanie (2015) Learning Mixed Membership Community Models in Social Tagging Networks through Tensor Methods. . (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20190401-162928669

[img] PDF - Submitted Version
See Usage Policy.

468Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20190401-162928669

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.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1503.04567arXivDiscussion Paper
Additional Information:A. Anandkumar is supported in part by Microsoft Faculty Fellowship, NSF Career award CCF-1254106, NSF Award CCF-1219234, and ARO YIP Award W911NF-13-1-0084. H. Sedghi is supported by ONR Award N00014-14-1-0665. The authors thank Majid Janzamin for detailed discussion on rank test analysis. The authors thank Rong Ge and Yash Deshpande for extensive initial discussions during the visit of AA to Microsoft Research New England in Summer 2013 regarding the pairwise mixed membership models without the Dirichlet assumption. The authors also acknowledge detailed discussions with Kamalika Chaudhuri regarding analysis of spectral clustering.
Funders:
Funding AgencyGrant Number
Microsoft Faculty FellowshipUNSPECIFIED
NSFCCF-1254106
NSFCCF-1219234
Army Research Office (ARO)W911NF-13-1-0084
Office of Naval Research (ONR)N00014-14-1-0665
Subject Keywords:Community models, social tagging systems/folksonomies, mixed membership models, tensor decomposition methods
Record Number:CaltechAUTHORS:20190401-162928669
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20190401-162928669
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:94347
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:02 Apr 2019 23:02
Last Modified:02 Apr 2019 23:02

Repository Staff Only: item control page