Preserving Link Privacy in Social Network Based Systems

Abstract

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.

16 pages, 15 figures

References in corpus (3)

• De-anonymizing Social Networks
• X-Vine: Secure and Pseudonymous Routing Using Social Networks
• Anonymity in the Wild: Mixes on unstructured networks

Cited by in corpus (14)

• Systematizing Decentralization and Privacy: Lessons from 15 Years of Research and Deployments
• Privacy in Social Media: Identification, Mitigation and Applications
• Publishing Community-Preserving Attributed Social Graphs with a Differential Privacy Guarantee
• An Efficient and Robust Social Network De-anonymization Attack
• walk2friends: Inferring Social Links from Mobility Profiles
• Rethinking $(k,\ell )$-anonymity in social graphs: $(k,\ell )$-adjacency anonymity and $(k,\ell )$-(adjacency) anonymous transformations
• Using Metrics Suites to Improve the Measurement of Privacy in Graphs
• Robust active attacks on social graphs
• Release Connection Fingerprints in Social Networks Using Personalized Differential Privacy
• LinkMirage: How to Anonymize Links in Dynamic Social Systems
• On Privacy and Confidentiality of Communications in Organizational Graphs
• Target Privacy Preserving for Social Networks
• Quantification of De-anonymization Risks in Social Networks
• Anonymizing Social Graphs via Uncertainty Semantics