  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.
