Document Detail


On Learning Cluster Coefficient of Private Networks.
MedLine Citation:
PMID:  24429843     Owner:  NLM     Status:  Publisher    
Abstract/OtherAbstract:
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 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 1, …, fm connected by basic mathematical operations (e.g., addition, subtraction, multiplication, division), then perturb the output of each fi with Laplace noise derived from its own sensitivity value and the distributed privacy threshold ε i , and finally combine those perturbed fi 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 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:
Yue Wang; Xintao Wu; Jun Zhu; Yang Xiang
Related Documents :
24696823 - Accuracy and precision of polyurethane dental arch models fabricated using a three-dime...
23938923 - Phantom study of tear film dynamics with optical coherence tomography and maximum-likel...
24101633 - Elongation as a factor in artefacts of humans and other animals: an acheulean example i...
Publication Detail:
Type:  JOURNAL ARTICLE    
Journal Detail:
Title:  Social network analysis and mining     Volume:  -     ISSN:  1869-5450     ISO Abbreviation:  Soc Netw Anal Min     Publication Date:  2012  
Date Detail:
Created Date:  2014-1-16     Completed Date:  -     Revised Date:  -    
Medline Journal Info:
Nlm Unique ID:  101616226     Medline TA:  Soc Netw Anal Min     Country:  -    
Other Details:
Languages:  ENG     Pagination:  395-402     Citation Subset:  -    
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms
Descriptor/Qualifier:

From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine


Previous Document:  Superior asymmetric supercapacitor based on Ni-Co oxide nanosheets and carbon nanorods.
Next Document:  The dynamics of toxic and nontoxic Microcystis during bloom in the large shallow lake, Lake Taihu, C...