Publishing Graph Node Strength Histogram with Edge Differential Privacy

被引：8

作者：

Qian, Qing ^{[1
]}

Li, Zhixu ^{[1
]}

Zhao, Pengpeng ^{[1
]}

Chen, Wei ^{[1
]}

Yin, Hongzhi ^{[2
]}

Zhao, Lei ^{[1
]}

机构：

[1] Soochow Univ, Sch Comp Sci & Technol, Suzhou, Peoples R China

[2] Univ Queensland, Sch Informat Technol & Elect Engn Brisbane, St Lucia, Qld, Australia

来源：

DATABASE SYSTEMS FOR ADVANCED APPLICATIONS (DASFAA 2018), PT II | 2018年 / 10828卷

基金：

中国国家自然科学基金;

关键词：

Differential privacy; Node strength; Histogram publishing;

D O I：

10.1007/978-3-319-91458-9_5

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Protecting the private graph data while releasing accurate estimate of the data is one of the most challenging problems in data privacy. Node strength combines the topological information with the weight distribution of the weighted graph in a natural way. Since an edge in graph data oftentimes represents relationship between two nodes, edge-differential privacy (edge-DP) can protect relationship between two entities from being disclosed. In this paper, we investigate the problem of publishing the node strength histogram of a private graph under edge-DP. We propose two clustering approaches based on sequence-aware and local density to aggregate histogram. Our experimental study demonstrates that our approaches can greatly reduce the error of approximating the true node strength histogram.

引用

页码：75 / 91

页数：17

共 28 条

[1] Differentially Private Histogram Publishing through Lossy Compression [J].

Acs, Gergely ;

Castelluccia, Claude ;

Chen, Rui .

12TH IEEE INTERNATIONAL CONFERENCE ON DATA MINING (ICDM 2012), 2012, :1-10

[2]

[Anonymous], 2011, ACM SIGCOMM INT MEAS

[3]

[Anonymous], 2007, P 16 INT C WORLD WID

[4] Publishing Graph Degree Distribution with Node Differential Privacy [J].

Day, Wei-Yen ;

Li, Ninghui ;

Lyu, Min .

SIGMOD'16: PROCEEDINGS OF THE 2016 INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, 2016, :123-138

[5]

Dwork C, 2006, LECT NOTES COMPUT SC, P1

[6] A Firm Foundation for Private Data Analysis [J].

Dwork, Cynthia .

COMMUNICATIONS OF THE ACM, 2011, 54 (01) :86-95

[7] Accurate Estimation of the Degree Distribution of Private Networks [J].

Hay, Michael ;

Li, Chao ;

Miklau, Gerome ;

Jensen, David .

2009 9TH IEEE INTERNATIONAL CONFERENCE ON DATA MINING, 2009, :169-178

[8] Analyzing Graphs with Node Differential Privacy [J].

Kasiviswanathan, Shiva Prasad ;

Nissim, Kobbi ;

Raskhodnikova, Sofya ;

Smith, Adam .

THEORY OF CRYPTOGRAPHY (TCC 2013), 2013, 7785 :457-476

[9] Towards an Axiomatization of Statistical Privacy and Utility [J].

Kifer, Daniel ;

Lin, Bing-Rong .

PODS 2010: PROCEEDINGS OF THE TWENTY-NINTH ACM SIGMOD-SIGACT-SIGART SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS, 2010, :147-158

[10] Empirical analysis of an evolving social network [J].

Kossinets, G ;

Watts, DJ .

SCIENCE, 2006, 311 (5757) :88-90

← 1 2 3 →