Noname manuscript No. (will be inserted by the editor) Correlated Network Data Publication via Differential Privacy

Abstract With the increasing prevalence of informa-tion networks, research on privacy-preserving network data publishing has received substantial attention re-cently. There are two streams of relevant research, tar-geting different privacy requirements. A large body of existing works focus on preventing node re-identification against adversaries with structural background knowl-edge, while some other studies aim to thwart edge dis-closure. In general, the line of research on preventing edge disclosure is less fruitful, largely due to lack of a formal privacy model. The recent emergence of dif-ferential privacy has shown great promise for rigorous prevention of edge disclosure. Yet recent research indi-cates that differential privacy is vulnerable to data cor-relation, which hinders its application to network data that may be inherently correlated. In this paper, we show that differential privacy could be tuned to provide provable privacy guarantees even in the correlated setting by introducing an extra parame-ter, which measures the extent of correlation. We sub-sequently provide a holistic solution for non-interactive network data publication. First, we generate a private vertex labeling for a given network dataset to make the corresponding adjacency matrix form dense clus