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

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.
978-1-7281-6739-8
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: http://hdl.handle.net/11383/2095696
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

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