Social network providers anonymize graphs storing users' relationships to protect users from being re-identified. Despite the fact that most of the relationships are directed (e.g., follows), few works (e.g., the Paired-degree [1] and K-In&Out-Degree Anonymity [2]) have been designed to work with directed graphs. In this paper, we show that given a graph, DGA [1]and DSNDG-KIODA [2] are not always able to generate its anonymized version. We overcome this limitation by presenting the Cluster-based Directed Graph Anonymization Algorithm(CDGA) and prove that, by choosing the appropriate parameters, CDGA can generate an anonymized graph satisfying both the Paired k-degree [1] and K-In&Out-Degree Anonymity [2]. Also, we present the Out-and In-Degree Information Loss Metric to minimize the number of changes made to anonymize the graph. We conduct extensive experiments on three real-life data sets to evaluate the effectiveness of CDGA and compare the quality of the graphs anonymized by CDGA, DGA, and DSNDG-KIODA. The experimental results show that we can generate anonymized graphs, by modifying less than 0.007% of edges in the original graph.

Cluster-based anonymization of directed graphs

Carminati B.
;
Ferrari E.
2019-01-01

Abstract

Social network providers anonymize graphs storing users' relationships to protect users from being re-identified. Despite the fact that most of the relationships are directed (e.g., follows), few works (e.g., the Paired-degree [1] and K-In&Out-Degree Anonymity [2]) have been designed to work with directed graphs. In this paper, we show that given a graph, DGA [1]and DSNDG-KIODA [2] are not always able to generate its anonymized version. We overcome this limitation by presenting the Cluster-based Directed Graph Anonymization Algorithm(CDGA) and prove that, by choosing the appropriate parameters, CDGA can generate an anonymized graph satisfying both the Paired k-degree [1] and K-In&Out-Degree Anonymity [2]. Also, we present the Out-and In-Degree Information Loss Metric to minimize the number of changes made to anonymize the graph. We conduct extensive experiments on three real-life data sets to evaluate the effectiveness of CDGA and compare the quality of the graphs anonymized by CDGA, DGA, and DSNDG-KIODA. The experimental results show that we can generate anonymized graphs, by modifying less than 0.007% of edges in the original graph.
2019
Proceedings - 2019 IEEE 5th International Conference on Collaboration and Internet Computing, CIC 2019
978-1-7281-6739-8
5th IEEE International Conference on Collaboration and Internet Computing, CIC 2019
usa
2019
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11383/2095696
 Attenzione

L'Ateneo sottopone a validazione solo i file PDF allegati

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact