2012/08/30 by Prateek Mittal, Mittal, Prateek, Charalampos Papamanthou +3 · 93 citations
Computer Science · Social Sciences · #Adversary #Computer network #Computer science #Computer security #Graph #Internet Traffic Analysis and Secure E-voting #Link (geometry) #Privacy, Security, and Data Protection #Privacy-Preserving Technologies in Data #Social graph #Social media #Social network (sociolinguistics) #Theoretical computer science #World Wide Web #cs.CR #cs.SI
paper · pdf · doi:10.48550/arxiv.1208.6189
published in arXiv (Cornell University) (Cornell University) · 16 pages, 15 figures
arxiv created 2012/08/30 · openalex publication_date 2012/08/30 · arxiv updated 2012/08/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
A growing body of research leverages social network based trust relationships to improve the functionality of the system. However, these systems expose users' trust relationships, which is considered sensitive information in today's society, to an adversary. In this work, we make the following contributions. First, we propose an algorithm that perturbs the structure of a social graph in order to provide link privacy, at the cost of slight reduction in the utility of the social graph. Second we define general metrics for characterizing the utility and privacy of perturbed graphs. Third, we evaluate the utility and privacy of our proposed algorithm using real world social graphs. Finally, we demonstrate the applicability of our perturbation algorithm on a broad range of secure systems, including Sybil defenses and secure routing.