A differentially private estimator for the stochastic Kronecker graph model

We consider the problem of making graph databases such as social networks available to researchers for knowledge discovery while providing privacy to the participating entities. We use a parametric graph model, the stochastic Kronecker graph model, to model the observed graph and construct an estimator of the "true parameter" in a way that both satisfies the rigorous requirements of differential privacy and demonstrates experimental utility on several important graph statistics. The estimator, which may then be published, defines a probability distribution on graphs. Sampling such a distribution yields a synthetic graph that mimics important properties of the original sensitive graph and consequently, could be useful for knowledge discovery.