On the k-anonymization of time-varying and multi-layer social graphs

Luca Rossi, Mirco Musolesi, Andrea Torsello

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The popularity of online social media platforms provides an unprecedented opportunity to study real-world complex networks of interactions. However, releasing this data to researchers and the public comes at the cost of potentially exposing private and sensitive user information. It has been shown that a naive anonymization of a network by removing the identity of the nodes is not sufficient to preserve users’ privacy. In order to deal with malicious attacks, k -anonymity solutions have been proposed to partially obfuscate topological information that can be used to infer nodes’ identity. In this paper, we study the problem of ensuring k anonymity in time-varying graphs, i.e., graphs with a structure that changes over time, and multi-layer graphs, i.e., graphs with multiple types of links. More specifically, we examine the case in which the attacker has access to the degree of the nodes. The goal is to generate a new graph where, given the degree of a node in each (temporal) layer of the graph, such a node remains indistinguishable from other k-1 nodes in the graph. In order to achieve this, we find the optimal partitioning of the graph nodes such that the cost of anonymizing the degree information within each group is minimum. We show that this reduces to a special case of a Generalized Assignment Problem, and we propose a simple yet effective algorithm to solve it. Finally, we introduce an iterated linear programming approach to enforce the realizability of the anonymized degree sequences. The efficacy of the method is assessed through an extensive set of experiments on synthetic and real-world graphs.
Original languageEnglish
Title of host publicationProceedings of the 9th International AAAI Conference on Web and Social Media (AAAI ICWSM'15)
Number of pages10
Publication statusPublished - 2015
Event9th International AAAI Conference on Web and Social Media - Oxford, United Kingdom
Duration: 26 May 201529 May 2015

Conference

Conference9th International AAAI Conference on Web and Social Media
Abbreviated titleICWSM-15
CountryUnited Kingdom
CityOxford
Period26/05/1529/05/15

Fingerprint

Complex networks
Linear programming
Costs
Experiments

Bibliographical note

© 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Cite this

Rossi, L., Musolesi, M., & Torsello, A. (2015). On the k-anonymization of time-varying and multi-layer social graphs. In Proceedings of the 9th International AAAI Conference on Web and Social Media (AAAI ICWSM'15)
Rossi, Luca ; Musolesi, Mirco ; Torsello, Andrea. / On the k-anonymization of time-varying and multi-layer social graphs. Proceedings of the 9th International AAAI Conference on Web and Social Media (AAAI ICWSM'15). 2015.
@inproceedings{9be943fc0ac74ebebb9a940a8dd541e3,
title = "On the k-anonymization of time-varying and multi-layer social graphs",
abstract = "The popularity of online social media platforms provides an unprecedented opportunity to study real-world complex networks of interactions. However, releasing this data to researchers and the public comes at the cost of potentially exposing private and sensitive user information. It has been shown that a naive anonymization of a network by removing the identity of the nodes is not sufficient to preserve users’ privacy. In order to deal with malicious attacks, k -anonymity solutions have been proposed to partially obfuscate topological information that can be used to infer nodes’ identity. In this paper, we study the problem of ensuring k anonymity in time-varying graphs, i.e., graphs with a structure that changes over time, and multi-layer graphs, i.e., graphs with multiple types of links. More specifically, we examine the case in which the attacker has access to the degree of the nodes. The goal is to generate a new graph where, given the degree of a node in each (temporal) layer of the graph, such a node remains indistinguishable from other k-1 nodes in the graph. In order to achieve this, we find the optimal partitioning of the graph nodes such that the cost of anonymizing the degree information within each group is minimum. We show that this reduces to a special case of a Generalized Assignment Problem, and we propose a simple yet effective algorithm to solve it. Finally, we introduce an iterated linear programming approach to enforce the realizability of the anonymized degree sequences. The efficacy of the method is assessed through an extensive set of experiments on synthetic and real-world graphs.",
author = "Luca Rossi and Mirco Musolesi and Andrea Torsello",
note = "{\circledC} 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.",
year = "2015",
language = "English",
booktitle = "Proceedings of the 9th International AAAI Conference on Web and Social Media (AAAI ICWSM'15)",

}

Rossi, L, Musolesi, M & Torsello, A 2015, On the k-anonymization of time-varying and multi-layer social graphs. in Proceedings of the 9th International AAAI Conference on Web and Social Media (AAAI ICWSM'15). 9th International AAAI Conference on Web and Social Media, Oxford, United Kingdom, 26/05/15.

On the k-anonymization of time-varying and multi-layer social graphs. / Rossi, Luca; Musolesi, Mirco; Torsello, Andrea.

Proceedings of the 9th International AAAI Conference on Web and Social Media (AAAI ICWSM'15). 2015.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - On the k-anonymization of time-varying and multi-layer social graphs

AU - Rossi, Luca

AU - Musolesi, Mirco

AU - Torsello, Andrea

N1 - © 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

PY - 2015

Y1 - 2015

N2 - The popularity of online social media platforms provides an unprecedented opportunity to study real-world complex networks of interactions. However, releasing this data to researchers and the public comes at the cost of potentially exposing private and sensitive user information. It has been shown that a naive anonymization of a network by removing the identity of the nodes is not sufficient to preserve users’ privacy. In order to deal with malicious attacks, k -anonymity solutions have been proposed to partially obfuscate topological information that can be used to infer nodes’ identity. In this paper, we study the problem of ensuring k anonymity in time-varying graphs, i.e., graphs with a structure that changes over time, and multi-layer graphs, i.e., graphs with multiple types of links. More specifically, we examine the case in which the attacker has access to the degree of the nodes. The goal is to generate a new graph where, given the degree of a node in each (temporal) layer of the graph, such a node remains indistinguishable from other k-1 nodes in the graph. In order to achieve this, we find the optimal partitioning of the graph nodes such that the cost of anonymizing the degree information within each group is minimum. We show that this reduces to a special case of a Generalized Assignment Problem, and we propose a simple yet effective algorithm to solve it. Finally, we introduce an iterated linear programming approach to enforce the realizability of the anonymized degree sequences. The efficacy of the method is assessed through an extensive set of experiments on synthetic and real-world graphs.

AB - The popularity of online social media platforms provides an unprecedented opportunity to study real-world complex networks of interactions. However, releasing this data to researchers and the public comes at the cost of potentially exposing private and sensitive user information. It has been shown that a naive anonymization of a network by removing the identity of the nodes is not sufficient to preserve users’ privacy. In order to deal with malicious attacks, k -anonymity solutions have been proposed to partially obfuscate topological information that can be used to infer nodes’ identity. In this paper, we study the problem of ensuring k anonymity in time-varying graphs, i.e., graphs with a structure that changes over time, and multi-layer graphs, i.e., graphs with multiple types of links. More specifically, we examine the case in which the attacker has access to the degree of the nodes. The goal is to generate a new graph where, given the degree of a node in each (temporal) layer of the graph, such a node remains indistinguishable from other k-1 nodes in the graph. In order to achieve this, we find the optimal partitioning of the graph nodes such that the cost of anonymizing the degree information within each group is minimum. We show that this reduces to a special case of a Generalized Assignment Problem, and we propose a simple yet effective algorithm to solve it. Finally, we introduce an iterated linear programming approach to enforce the realizability of the anonymized degree sequences. The efficacy of the method is assessed through an extensive set of experiments on synthetic and real-world graphs.

M3 - Conference contribution

BT - Proceedings of the 9th International AAAI Conference on Web and Social Media (AAAI ICWSM'15)

ER -

Rossi L, Musolesi M, Torsello A. On the k-anonymization of time-varying and multi-layer social graphs. In Proceedings of the 9th International AAAI Conference on Web and Social Media (AAAI ICWSM'15). 2015