Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communities

Abstract

We propose a novel statistical model for sparse networks with overlapping community structure. The model is based on representing the graph as an exchangeable point process, and naturally generalizes existing probabilistic models with overlapping block-structure to the sparse regime. Our construction builds on vectors of completely random measures, and has interpretable parameters, each node being assigned a vector representing its level of affiliation to some latent communities. We develop methods for simulating this class of random graphs, as well as to perform posterior inference. We show that the proposed approach can recover interpretable structure from two real-world networks and can handle graphs with thousands of nodes and tens of thousands of edges.

References in corpus (8)

• Power-law distributions in empirical data
• Stochastic blockmodels and community structure in networks
• Estimating the number of communities in a network
• Poisson Process Partition Calculus with applications to Exchangeable models and Bayesian Nonparametrics
• Sparse exchangeable graphs and their limits via graphon processes
• Infinite Edge Partition Models for Overlapping Community Detection and Link Prediction
• Bayesian inference with dependent normalized completely random measures
• Poisson Latent Feature Calculus for Generalized Indian Buffet Processes

Cited by in corpus (6)

• Overlapping Community Detection with Graph Neural Networks
• Sampling perspectives on sparse exchangeable graphs
• Softplus Regressions and Convex Polytopes
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• Edge-exchangeable graphs and sparsity (NIPS 2016)
• Exchangeable modelling of relational data: checking sparsity, train-test splitting, and sparse exchangeable Poisson matrix factorization