Research Article
\(\mathbb {PSG}\): Local Privacy Preserving Synthetic Social Graph Generation
@INPROCEEDINGS{10.1007/978-3-030-92635-9_23, author={Hongyu Huang and Yao Yang and Yantao Li}, title={\textbackslash(\textbackslashmathbb \{PSG\}\textbackslash): Local Privacy Preserving Synthetic Social Graph Generation}, proceedings={Collaborative Computing: Networking, Applications and Worksharing. 17th EAI International Conference, CollaborateCom 2021, Virtual Event, October 16-18, 2021, Proceedings, Part I}, proceedings_a={COLLABORATECOM}, year={2022}, month={1}, keywords={Social networks Local differential privacy Synthetic graph generation}, doi={10.1007/978-3-030-92635-9_23} }- Hongyu Huang
Yao Yang
Yantao Li
Year: 2022
\(\mathbb {PSG}\): Local Privacy Preserving Synthetic Social Graph Generation
COLLABORATECOM
Springer
DOI: 10.1007/978-3-030-92635-9_23
Abstract
Social graph, as a representation of the network topology, contains users’ social relationship. In order to obtain a social graph, a server requires users to submit their relationships. As we know, using or publishing social graph will cause privacy leakage to users. For this sake, it is necessary to generate synthetic social graph for various usages. In this paper, we propose(\mathbb {PSG}), a local Privacy Preserving Synthetic Social Graph Generation method. In order to protect users’ privacy, we utilize the local differential privacy model and a truncated Laplace mechanism to allow users to perturb their own data before submission. We then model the graph generation as a combinatorial optimization problem and design a greedy algorithm to maximize the utility of the generated graph. Through theoretical analysis and extensive experiments, we show that our method satisfies local differential privacy as well as maintains attributes of the original social graph.
