Scalable inference of overlapping communities

Prem Gopalan; David Mimno; Sean M. Gerrish; Michael Joseph Freedman; David M. Blei

Scalable inference of overlapping communities

Prem Gopalan, David Mimno, Sean M. Gerrish, Michael Joseph Freedman, David M. Blei

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

56 Scopus citations

Abstract

We develop a scalable algorithm for posterior inference of overlapping communities in large networks. Our algorithm is based on stochastic variational inference in the mixed-membership stochastic blockmodel (MMSB). It naturally interleaves subsampling the network with estimating its community structure. We apply our algorithm on ten large, real-world networks with up to 60,000 nodes. It converges several orders of magnitude faster than the state-of-the-art algorithm for MMSB, finds hundreds of communities in large real-world networks, and detects the true communities in 280 benchmark networks with equal or better accuracy compared to other scalable algorithms.

Original language	English (US)
Title of host publication	Advances in Neural Information Processing Systems 25
Subtitle of host publication	26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012
Pages	2249-2257
Number of pages	9
Volume	3
State	Published - Dec 1 2012
Event	26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012 - Lake Tahoe, NV, United States Duration: Dec 3 2012 → Dec 6 2012

Other

Other	26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012
Country/Territory	United States
City	Lake Tahoe, NV
Period	12/3/12 → 12/6/12

All Science Journal Classification (ASJC) codes

Computer Networks and Communications
Information Systems
Signal Processing

Cite this

@inproceedings{afe8aee8b887486187cac6c264d45686,

title = "Scalable inference of overlapping communities",

abstract = "We develop a scalable algorithm for posterior inference of overlapping communities in large networks. Our algorithm is based on stochastic variational inference in the mixed-membership stochastic blockmodel (MMSB). It naturally interleaves subsampling the network with estimating its community structure. We apply our algorithm on ten large, real-world networks with up to 60,000 nodes. It converges several orders of magnitude faster than the state-of-the-art algorithm for MMSB, finds hundreds of communities in large real-world networks, and detects the true communities in 280 benchmark networks with equal or better accuracy compared to other scalable algorithms.",

author = "Prem Gopalan and David Mimno and Gerrish, {Sean M.} and Freedman, {Michael Joseph} and Blei, {David M.}",

year = "2012",

month = dec,

day = "1",

language = "English (US)",

isbn = "9781627480031",

volume = "3",

pages = "2249--2257",

booktitle = "Advances in Neural Information Processing Systems 25",

note = "26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012 ; Conference date: 03-12-2012 Through 06-12-2012",

}

Gopalan, P, Mimno, D, Gerrish, SM, Freedman, MJ & Blei, DM 2012, Scalable inference of overlapping communities. in Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012. vol. 3, pp. 2249-2257, 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012, Lake Tahoe, NV, United States, 12/3/12.

TY - GEN

T1 - Scalable inference of overlapping communities

AU - Gopalan, Prem

AU - Mimno, David

AU - Gerrish, Sean M.

AU - Freedman, Michael Joseph

AU - Blei, David M.

PY - 2012/12/1

Y1 - 2012/12/1

N2 - We develop a scalable algorithm for posterior inference of overlapping communities in large networks. Our algorithm is based on stochastic variational inference in the mixed-membership stochastic blockmodel (MMSB). It naturally interleaves subsampling the network with estimating its community structure. We apply our algorithm on ten large, real-world networks with up to 60,000 nodes. It converges several orders of magnitude faster than the state-of-the-art algorithm for MMSB, finds hundreds of communities in large real-world networks, and detects the true communities in 280 benchmark networks with equal or better accuracy compared to other scalable algorithms.

AB - We develop a scalable algorithm for posterior inference of overlapping communities in large networks. Our algorithm is based on stochastic variational inference in the mixed-membership stochastic blockmodel (MMSB). It naturally interleaves subsampling the network with estimating its community structure. We apply our algorithm on ten large, real-world networks with up to 60,000 nodes. It converges several orders of magnitude faster than the state-of-the-art algorithm for MMSB, finds hundreds of communities in large real-world networks, and detects the true communities in 280 benchmark networks with equal or better accuracy compared to other scalable algorithms.

UR - http://www.scopus.com/inward/record.url?scp=84877735139&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84877735139&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84877735139

SN - 9781627480031

VL - 3

SP - 2249

EP - 2257

BT - Advances in Neural Information Processing Systems 25

T2 - 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012

Y2 - 3 December 2012 through 6 December 2012

ER -

Scalable inference of overlapping communities

Abstract

Other

All Science Journal Classification (ASJC) codes

Other files and links

Cite this