TY - GEN
T1 - Delineating social network data anonymization via random edge perturbation
AU - Xue, Mingqiang
AU - Karras, Panagiotis
AU - Raïssi, Chedy
AU - Kalnis, Panos
AU - Pung, Hungkeng
N1 - KAUST Repository Item: Exported on 2020-10-01
PY - 2012
Y1 - 2012
N2 - Social network data analysis raises concerns about the privacy of related entities or individuals. To address this issue, organizations can publish data after simply replacing the identities of individuals with pseudonyms, leaving the overall structure of the social network unchanged. However, it has been shown that attacks based on structural identification (e.g., a walk-based attack) enable an adversary to re-identify selected individuals in an anonymized network. In this paper we explore the capacity of techniques based on random edge perturbation to thwart such attacks. We theoretically establish that any kind of structural identification attack can effectively be prevented using random edge perturbation and show that, surprisingly, important properties of the whole network, as well as of subgraphs thereof, can be accurately calculated and hence data analysis tasks performed on the perturbed data, given that the legitimate data recipient knows the perturbation probability as well. Yet we also examine ways to enhance the walk-based attack, proposing a variant we call probabilistic attack. Nevertheless, we demonstrate that such probabilistic attacks can also be prevented under sufficient perturbation. Eventually, we conduct a thorough theoretical study of the probability of success of any}structural attack as a function of the perturbation probability. Our analysis provides a powerful tool for delineating the identification risk of perturbed social network data; our extensive experiments with synthetic and real datasets confirm our expectations. © 2012 ACM.
AB - Social network data analysis raises concerns about the privacy of related entities or individuals. To address this issue, organizations can publish data after simply replacing the identities of individuals with pseudonyms, leaving the overall structure of the social network unchanged. However, it has been shown that attacks based on structural identification (e.g., a walk-based attack) enable an adversary to re-identify selected individuals in an anonymized network. In this paper we explore the capacity of techniques based on random edge perturbation to thwart such attacks. We theoretically establish that any kind of structural identification attack can effectively be prevented using random edge perturbation and show that, surprisingly, important properties of the whole network, as well as of subgraphs thereof, can be accurately calculated and hence data analysis tasks performed on the perturbed data, given that the legitimate data recipient knows the perturbation probability as well. Yet we also examine ways to enhance the walk-based attack, proposing a variant we call probabilistic attack. Nevertheless, we demonstrate that such probabilistic attacks can also be prevented under sufficient perturbation. Eventually, we conduct a thorough theoretical study of the probability of success of any}structural attack as a function of the perturbation probability. Our analysis provides a powerful tool for delineating the identification risk of perturbed social network data; our extensive experiments with synthetic and real datasets confirm our expectations. © 2012 ACM.
UR - http://hdl.handle.net/10754/564506
UR - http://dl.acm.org/citation.cfm?doid=2396761.2396823
UR - http://www.scopus.com/inward/record.url?scp=84871068435&partnerID=8YFLogxK
U2 - 10.1145/2396761.2396823
DO - 10.1145/2396761.2396823
M3 - Conference contribution
SN - 9781450311564
SP - 475
EP - 484
BT - Proceedings of the 21st ACM international conference on Information and knowledge management - CIKM '12
PB - Association for Computing Machinery (ACM)
ER -