title: On Learning Cluster Coefficient of Private Networks.
abstract: Enabling accurate analysis of social network data while preserving differential privacy has been challenging since graph features such as clustering coefficient or modularity often have high sensitivity, which is different from traditional aggregate functions (e.g., count and sum) on tabular data. In this paper, we treat a graph statistics as a functionfand develop a divide and conquer approach to enforce differential privacy. The basic procedure of this approach is to first decompose the target computationfinto several less complex unit computationsf1, …,fmconnected by basic mathematical operations (e.g., addition, subtraction, multiplication, division), then perturb the output of eachfiwith Laplace noise derived from its own sensitivity value and the distributed privacy threshold εi, and finally combine those perturbedfias the perturbed output of computationf. We examine how various operations affect the accuracy of complex computations. When unit computations have large global sensitivity values, we enforce the differential privacy by calibrating noise based on the smooth sensitivity, rather than the global sensitivity. By doing this, we achieve the strict differential privacy guarantee with smaller magnitude noise. We illustrate our approach by using clustering coefficient, which is a popular statistics used in social network analysis. Empirical evaluations on five real social networks and various synthetic graphs generated from three random graph models show the developed divide and conquer approach outperforms the direct approach.
authors.affiliation: University of North Carolina at Charlotte, USA, Tel.: +1-704-6878586.
authors.forename: Yue
authors.initials: Y
authors.lastname: Wang
authors.affiliation: University of North Carolina at Charlotte, USA, Tel.: +1-704-6878586.
authors.forename: Xintao
authors.initials: X
authors.lastname: Wu
authors.affiliation: University of North Carolina at Charlotte, USA, Tel.: +1-704-6878586.
authors.forename: Jun
authors.initials: J
authors.lastname: Zhu
authors.affiliation: Tongji University, Shanghai, China.
authors.forename: Yang
authors.initials: Y
authors.lastname: Xiang