Privacy-Preserving Triangle Counting in Large Graphs

Ding, X, Zhang, X, Bao, Z and Jin, H 2018, 'Privacy-Preserving Triangle Counting in Large Graphs', in Proceedings of the 27th ACM International Conference on Information and Knowledge Management (CIKM 2018), Torino, Italy, 22-26 October 2018, pp. 1283-1292.


Document type: Conference Paper
Collection: Conference Papers

Title Privacy-Preserving Triangle Counting in Large Graphs
Author(s) Ding, X
Zhang, X
Bao, Z
Jin, H
Year 2018
Conference name CIKM 2018
Conference location Torino, Italy
Conference dates 22-26 October 2018
Proceedings title Proceedings of the 27th ACM International Conference on Information and Knowledge Management (CIKM 2018)
Publisher ACM
Place of publication New York, United States
Start page 1283
End page 1292
Total pages 10
Abstract Triangle count is a critical parameter in mining relationships among people in social networks. However, directly publishing the findings obtained from triangle counts may bring potential privacy concern, which raises great challenges and opportunities for privacy-preserving triangle counting. In this paper, we choose to use differential privacy to protect triangle counting for large scale graphs. To reduce the large sensitivity caused in large graphs, we propose a novel graph projection method that can be used to obtain an upper bound for sensitivity in different distributions. In particular, we publish the triangle counts satisfying the node-differential privacy with two kinds of histograms: the triangle count distribution and the cumulative distribution. Moreover, we extend the research on privacy preserving triangle counting to one of its applications, the local clustering coefficient. Experimental results show that the cumulative distribution can fit the real statistical information better, and our proposed mechanism has achieved better accuracy for triangle counts while maintaining the requirement of differential privacy.
Subjects Database Management
DOI - identifier 10.1145/3269206.3271736
Copyright notice © 2018 Association for Computing Machinery
ISBN 9781450360142
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Altmetric details:
Access Statistics: 30 Abstract Views  -  Detailed Statistics
Created: Thu, 21 Feb 2019, 12:10:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us