Timezone: »

 
Poster
Thinned random measures for sparse graphs with overlapping communities
Federica Zoe Ricci · Michele Guindani · Erik Sudderth

Tue Nov 29 02:00 PM -- 04:00 PM (PST) @ Hall J #510
in Poster Session 2 »

Network models for exchangeable arrays, including most stochastic block models, generate dense graphs with a limited ability to capture many characteristics of real-world social and biological networks. A class of models based on completely random measures like the generalized gamma process (GGP) have recently addressed some of these limitations. We propose a framework for thinning edges from realizations of GGP random graphs that models observed links via nodes' overall propensity to interact, as well as the similarity of node memberships within a large set of latent communities. Our formulation allows us to learn the number of communities from data, and enables efficient Monte Carlo methods that scale linearly with the number of observed edges, and thus (unlike dense block models) sub-quadratically with the number of entities or nodes. We compare to alternative models for both dense and sparse networks, and demonstrate effective recovery of latent community structure for real-world networks with thousands of nodes.

Keywords: Bayesian Nonparametrics · generalized gamma process · sparse networks · stochastic blockmodels

Author Information

Federica Zoe Ricci (UC Irvine)
Michele Guindani (University of California, Irvine)
Erik Sudderth (University of California, Irvine)

More from the Same Authors