  We present a novel method for publishing differentially private synthetic
attributed graphs. Unlike preceding approaches, our method is able to preserve
the community structure of the original graph without sacrificing the ability
to capture global structural properties. Our proposal relies on C-AGM, a new
community-preserving generative model for attributed graphs. We equip C-AGM
with efficient methods for attributed graph sampling and parameter estimation.
For the latter, we introduce differentially private computation methods, which
allow us to release community-preserving synthetic attributed social graphs
with a strong formal privacy guarantee. Through comprehensive experiments, we
show that our new model outperforms its most relevant counterparts in
synthesising differentially private attributed social graphs that preserve the
community structure of the original graph, as well as degree sequences and
clustering coefficients.
