Skip to main content

A tensor spectral approach to learning mixed membership community models

Publication ,  Journal Article
Anandkumar, A; Ge, R; Hsu, D; Kakade, SM
Published in: Journal of Machine Learning Research
January 1, 2013

Detecting hidden communities from observed interactions is a classical problem. Theoretical analysis of community detection has so far been mostly limited to models with non-overlapping communities such as the stochastic block model. In this paper, we provide guaranteed community detection for a family of probabilistic network models with overlapping communities, termed as the mixed membership Dirichlet model, first introduced in Airoldi 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. Moreover, it contains the stochastic block model as a special case. We propose a unified approach to learning communities in these models via a tensor spectral decomposition approach. Our estimator uses low-order moment tensor of the observed network, consisting of 3-star counts. Our learning method is based on simple linear algebraic operations such as 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 for the special case of the (homogeneous) stochastic block model. © 2013 A. Anandkumar, R. Ge, D. Hsu & S.M. Kakade.

Duke Scholars

Published In

Journal of Machine Learning Research

EISSN

1533-7928

ISSN

1532-4435

Publication Date

January 1, 2013

Volume

30

Start / End Page

867 / 881

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 4905 Statistics
  • 4611 Machine learning
  • 17 Psychology and Cognitive Sciences
  • 08 Information and Computing Sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Anandkumar, A., Ge, R., Hsu, D., & Kakade, S. M. (2013). A tensor spectral approach to learning mixed membership community models. Journal of Machine Learning Research, 30, 867–881.
Anandkumar, A., R. Ge, D. Hsu, and S. M. Kakade. “A tensor spectral approach to learning mixed membership community models.” Journal of Machine Learning Research 30 (January 1, 2013): 867–81.
Anandkumar A, Ge R, Hsu D, Kakade SM. A tensor spectral approach to learning mixed membership community models. Journal of Machine Learning Research. 2013 Jan 1;30:867–81.
Anandkumar, A., et al. “A tensor spectral approach to learning mixed membership community models.” Journal of Machine Learning Research, vol. 30, Jan. 2013, pp. 867–81.
Anandkumar A, Ge R, Hsu D, Kakade SM. A tensor spectral approach to learning mixed membership community models. Journal of Machine Learning Research. 2013 Jan 1;30:867–881.

Published In

Journal of Machine Learning Research

EISSN

1533-7928

ISSN

1532-4435

Publication Date

January 1, 2013

Volume

30

Start / End Page

867 / 881

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 4905 Statistics
  • 4611 Machine learning
  • 17 Psychology and Cognitive Sciences
  • 08 Information and Computing Sciences