Privacy-Integrated Graph Clustering Through Differential Privacy.

Data mining tasks like graph clustering can automatically process a large amount of data and retrieve valuable information. However, publishing such graph clustering results also involves privacy risks. In particular, linking the result with available background knowledge can disclose private information of the data set. The strong privacy guarantees of the dierential privacy model allow coping with the arbitrarily large background knowledge of a potential adversary. As current denitions of neighboring graphs do not fulll the needs of graph clustering results, this paper proposes a new one. Furthermore, this paper proposes a graph clustering approach that guarantees 1-edge-dierentia l privacy for its results. Besides giving strong privacy guarantees, our approach is able to calculate usable results. Those guarantees are ensured by perturbing the input graph. We have thoroughly evaluated our approach on synthetic data as well as on real-world graphs.