Random clique covers for graphs with local density and global sparsity

Abstract

Large real-world graphs tend to be sparse, but they often contain many densely connected subgraphs and exhibit high clustering coefficients. While recent random graph models can capture this sparsity, they ignore the local density, or vice versa. We develop a Bayesian nonparametric graph model based on random edge clique covers, and show that this model can capture power law degree distribution, global sparsity and non-vanishing local clustering coefficient. This distribution can be used directly as a prior on observed graphs, or as part of a hierarchical Bayesian model for inferring latent graph structures.

arXiv commentAppears in UAI 2019. This version includes appendices

References in corpus (6)

• Community structure in social and biological networks
• Stochastic blockmodels and community structure in networks
• GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models
• Sparse graphs using exchangeable random measures
• Sparse exchangeable graphs and their limits via graphon processes
• Degree Relations of Triangles in Real-world Networks and Models

Cited by in corpus (2)

• Master equation analysis of mesoscopic localization in contagion dynamics on higher-order networks
• A simple bipartite graph projection model for clustering in networks