A Tensor Spectral Approach to Learning Mixed Membership Community Models

Add to your list(s) Download to your calendar using vCal

• Anandkumar , A (University of California, Irvine)
• Tuesday 13 August 2013, 10:00-10:45
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact Mustapha Amrani.

Stochastic Processes in Communication Sciences

Co-authors: Rong Ge (Princeton), Daniel Hsu (Microsoft Research), Sham Kakade (Microsoft Research)

Modeling community formation and detecting hidden communities in networks is a well studied problem. However, theoretical analysis of community detection has been mostly limited to models with non-overlapping communities such as the stochastic block model. In this paper, we remove this restriction, and consider a family of probabilistic network models with overlapping communities, termed as the mixed membership Dirichlet model, first introduced in Aioroldi et. al. 2008. This model allows for nodes to have fractional memberships in multiple communities and assumes that the community memberships are drawn from a Dirichlet distribution. 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 algebra 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. Additionally, our results match the best known scaling requirements in the special case of the stochastic block model.

Related Links http://newport.eecs.uci.edu/anandkumar/pubs/AnandkumarCommunity.pdf – manuscript

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.