Community Privacy using the Sparse Vector Technique for Graph Statistics

Hara Seon, Hyeongjun Choi, Baek Kyung Song, Ji Won Yoon

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Various attacks have occurred to extract information on a specific person from social networks. Differential privacy (DP) is one of the solutions for privacy disclosure issues. However, the privacy issue in social networks makes people reluctant to provide their data. This circumstance causes a lack of data for data analysis. DP in small data degrades data utility more than in big data when we add the same amount of noise. We propose Community Attributes Privacy-preserving Method (CAPM) using the sparse vector technique that maintains a constant privacy level even in small data to mitigate this issue in this paper. CAPM obfuscates raw graph data to protect the network structure in a small network. This technique can improve the data utility performance compared to the existing model. We also suggest a privacy parameter that sets the privacy budget based on the similarity of communities in a network to reflect the network topology and contribute to raising the accuracy of a synthetic graph. In a node privacy view, we inject noise into the edges of central nodes in a community. Finally, we evaluate CAPM with real networks regarding statistical utility and privacy protection. We show that CAPM has an error rate of the number of edges up to 20 percent and its structural entropy is less than 17 percent of the error rate on average. CAPM improves the average clustering coefficient by 82 percent from the recent modeling algorithm. In addition, a maximum 18 percent error rate in modularity outperforms the baseline whose 43 percent of error rate. The evaluation results show that the CAPM generates synthetic social graphs targeting their relations of communities and performs better in data utility.

Original languageEnglish
Title of host publicationESSE 2022 - 2022 3rd European Symposium on Software Engineering
PublisherAssociation for Computing Machinery
Number of pages9
ISBN (Electronic)9781450397308
Publication statusPublished - 2022 Oct 27
Event3rd European Symposium on Software Engineering, ESSE 2022 - Rome, Italy
Duration: 2022 Oct 272022 Oct 29

Publication series

NameACM International Conference Proceeding Series


Conference3rd European Symposium on Software Engineering, ESSE 2022

Bibliographical note

Funding Information:
This work was supported by Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea government(MSIT) (No.2021-0-00558, Development of national statistical analysis system using homomorphic encryption technology). Also, we thank to Mi Yeon Hong for editing this paper.

Publisher Copyright:
© 2022 ACM.


  • Differential Privacy
  • Privacy Preserving Graph
  • Social Network

ASJC Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications


Dive into the research topics of 'Community Privacy using the Sparse Vector Technique for Graph Statistics'. Together they form a unique fingerprint.

Cite this