On learning cluster coefficient of private network

Authors: Yue Wang Xintao Wu Jun Zhu Yang Xiang

Publish Date: 2013/07/16

Volume: 3, Issue: 4, Pages: 925-938

PDF Link

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 eg count and sum on tabular data In this paper we treat a graph statistics as a function f and develop a divide and conquer approach to enforce differential privacy The basic procedure of this approach is to first decompose the target computation f into several less complex unit computations f 1ldotsf m connected by basic mathematical operations eg addition subtraction multiplication division then perturb the output of each f i with Laplace noise derived from its own sensitivity value and the distributed privacy threshold epsilon i and finally combine those perturbed f i as the perturbed output of computation f 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 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 that the developed divide and conquer approach outperforms the direct approachThe conference version of this work was published in Wang et al 2012 This journal version contains significant extensions including detailed theoretical proofs and extensive empirical evaluations We would like to thank anonymous reviewers for their invaluable comments This work was supported in part by US National Science Foundation 0546027 0831204 0915059 1047621 US National Institutes of Health 1R01GM10330901A1 and the Shanghai Magnolia Science Technology Talent Fund 11BA1412600LS C s G = LS C G + s for s ≤ b ij because we may add one edge to complete a halfbuilt triangle involving edge i j which makes the sensitivity increased by at most one meanwhile LS CsG=LS CG+lfloorfracs+b ij2rfloor for s  b ij because we have to add two edges to form a triangle to make the sensitivity increased by one after completing all the b ij halfbuilt triangles involving edge i j Besides LS C s G ≤ GS C G = n − 1 So we have Eq 17In addition to the Proof of Result 2 given in Nissim et al 2007 LS N UpdeltasG=3cdotmax ineq jjinn c ijs because each of the two entries corresponding to vertex i and j will be decreased by at most max ineq jjinn c ijs when edge i j is deleted from G Besides there are max ineq jjinn c ijs other entries whose values will be decreased by one corresponding to the neighbors in common by vertex i and jIn general case LS N 3sG=LS N 3G+s for s ≤ b ij and LS N 3sG=LS N 3G+lfloorfracs+b ij2rfloor for s  b ij which are similar to those of LS C s G and LS N 3sGleq GS N 3G=2n4 So we have the form for LS N 3sG

Keywords: