A Probability Mapping-Based Privacy Preservation Method for Social Networks

Li, Qingru; Wang, Yahong; Wang, Fangwei; Tan, Zhiyuan; Wang, Changguang

Abstract

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.

• Presentation Conference Type: Conference Paper (Published)
• Conference Name: The 3rd International Conference on Ubiquitous Security 2023 (UbiSec-2023)
• Start Date: Nov 1, 2023
• End Date: Nov 3, 2023
• Acceptance Date: Oct 16, 2023
• Online Publication Date: Mar 13, 2024
• Publication Date: 2024
• Deposit Date: Oct 24, 2023
• Publicly Available Date: Mar 14, 2025
• Publisher: Springer
• Pages: 289-303
• ISBN: 978-981-97-1273-1
• DOI: https://doi.org/10.1007/978-981-97-1274-8_19
• Keywords: Differential Privacy, Multi-Armed Bandit, Mapping, Projection, Histogram, Social Networks
• Public URL: http://researchrepository.napier.ac.uk/Output/3221843
• Publisher URL: https://link.springer.com/conference/ubisec
• Related Public URLs: https://hpcn.exeter.ac.uk/ubisec2023/