Differentially Private Triangle Counting in Large Graphs

doi:10.1109/TKDE.2021.3052827

Differentially Private Triangle Counting in Large Graphs

2022-11-01

9

PRE

AI

DOI：10.1109/TKDE.2021.3052827

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

Privacy

Differential privacy

Sensitivity

Histograms

Publishing

Social networking (online)

Knowledge engineering

Differential privacy

triangle counting

large graph

Differentially Private Triangle Counting in Large Graphs

Abstract

Journal

Organization