Skip to main content
Journal cover image

The k-anonymity and l-diversity approaches for privacy preservation in social networks against neighborhood attacks

Publication ,  Journal Article
Zhou, B; Pei, J
Published in: Knowledge and Information Systems
January 1, 2011

Recently, more and more social network data have been published in one way or another. Preserving privacy in publishing social network data becomes an important concern. With some local knowledge about individuals in a social network, an adversary may attack the privacy of some victims easily. Unfortunately, most of the previous studies on privacy preservation data publishing can deal with relational data only, and cannot be applied to social network data. In this paper, we take an initiative toward preserving privacy in social network data. Specifically, we identify an essential type of privacy attacks: neighborhood attacks. If an adversary has some knowledge about the neighbors of a target victim and the relationship among the neighbors, the victim may be re-identified from a social network even if the victim's identity is preserved using the conventional anonymization techniques. To protect privacy against neighborhood attacks, we extend the conventional k-anonymity and l-diversity models from relational data to social network data. We show that the problems of computing optimal k-anonymous and l-diverse social networks are NP-hard. We develop practical solutions to the problems. The empirical study indicates that the anonymized social network data by our methods can still be used to answer aggregate network queries with high accuracy. © 2010 Springer-Verlag London Limited.

Duke Scholars

Published In

Knowledge and Information Systems

DOI

EISSN

0219-3116

ISSN

0219-1377

Publication Date

January 1, 2011

Volume

28

Issue

1

Start / End Page

47 / 77

Related Subject Headings

  • Information Systems
  • 46 Information and computing sciences
  • 0806 Information Systems
  • 0801 Artificial Intelligence and Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Zhou, B., & Pei, J. (2011). The k-anonymity and l-diversity approaches for privacy preservation in social networks against neighborhood attacks. Knowledge and Information Systems, 28(1), 47–77. https://doi.org/10.1007/s10115-010-0311-2
Zhou, B., and J. Pei. “The k-anonymity and l-diversity approaches for privacy preservation in social networks against neighborhood attacks.” Knowledge and Information Systems 28, no. 1 (January 1, 2011): 47–77. https://doi.org/10.1007/s10115-010-0311-2.
Zhou B, Pei J. The k-anonymity and l-diversity approaches for privacy preservation in social networks against neighborhood attacks. Knowledge and Information Systems. 2011 Jan 1;28(1):47–77.
Zhou, B., and J. Pei. “The k-anonymity and l-diversity approaches for privacy preservation in social networks against neighborhood attacks.” Knowledge and Information Systems, vol. 28, no. 1, Jan. 2011, pp. 47–77. Scopus, doi:10.1007/s10115-010-0311-2.
Zhou B, Pei J. The k-anonymity and l-diversity approaches for privacy preservation in social networks against neighborhood attacks. Knowledge and Information Systems. 2011 Jan 1;28(1):47–77.
Journal cover image

Published In

Knowledge and Information Systems

DOI

EISSN

0219-3116

ISSN

0219-1377

Publication Date

January 1, 2011

Volume

28

Issue

1

Start / End Page

47 / 77

Related Subject Headings

  • Information Systems
  • 46 Information and computing sciences
  • 0806 Information Systems
  • 0801 Artificial Intelligence and Image Processing