| Title | Privacy-Preserving Triangle Counting in Large Graphs |
| Publication Type | Conference Paper |
| Year of Publication | 2018 |
| Authors | Ding, Xiaofeng, Zhang, Xiaodong, Bao, Zhifeng, Jin, Hai |
| Conference Name | Proceedings of the 27th ACM International Conference on Information and Knowledge Management |
| Publisher | ACM |
| Conference Location | New York, NY, USA |
| ISBN Number | 978-1-4503-6014-2 |
| Keywords | compositionality, Data Sanitization, Differential privacy, Human Behavior, large graph, privacy, pubcrawl, resilience, triangle counting |
| 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. |
| URL | http://doi.acm.org/10.1145/3269206.3271736 |
| DOI | 10.1145/3269206.3271736 |
| Citation Key | ding_privacy-preserving_2018 |
Privacy-Preserving Triangle Counting in Large Graphs