Edinburgh Napier University

  The mining and analysis of social networks can bring significant economic and social benefits. However, it also poses a risk of privacy leakages. Differential privacy is a de facto standard to prevent such leaks, but it suffers from the high sensitivity of query functions. Although projection is a technique that can reduce this sensitivity, existing methods still struggle to maintain a satisfactory level of sensitivity in query functions. This results in lower data utility and an inevitable risk of privacy leakage. To prevent the disclosure of user privacy, we need to significantly reduce the sensitivity of the query functions and minimize the error of the projected values with respect to the original values. To address this issue, we first explore the influence of mapping and projection on reducing the sensitivity of query functions. We then propose a Probability Mapping (PM) algorithm, based on multi-armed bandit, which however tends to generate mapped graphs with a wide range of degrees and containing considerable nodes with high degrees. Thus, we develop a new Probability Projection (PP) algorithm to overcome these weaknesses. Finally, we propose four histogram publishing algorithms built upon PM and PP, namely PMTC, PPTC, PMCTC and PPCTC. Extensive experimental results on three different sized datasets show that PM and PP not only retain more edge information and reduce the error but also improve the data availability.