EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

3120. Anonymizing networks via mathematical programming

Invited abstract in session TC-29: Exact Algorithms and Formulations for Network Optimization Problems, stream Combinatorial Optimization.

Tuesday, 12:30-14:00
Room: 157 (building: 208)

Authors (first author is the speaker)

1. Carmine Sorgente
Department of Mathematics, University of Salerno
2. Raffaele Cerulli
Department of Mathematics, University of Salerno
3. Ivana Ljubic
IDS, ESSEC Business School of Paris

Abstract

Social network data sets are often published and used for analysis purposes in many application domains. This may raise privacy issues, as simply hiding the identity of the users does not prevent an adversary from tracing back to the real-world entities associated with certain nodes of the network having sufficiently distinguishable features from others. To protect individuals' privacy, networks are commonly anonymized before publication.
In this context, the k-degree anonymization problem, originally introduced by Liu and Terzi in 2008, aims to identify the smallest set of modifications of the edge set of a network needed to make it k-degree anonymous, meaning that each user of the anonymized network will have the same number of connections as at least other k-1 users. In such a definition, different k values reflect different privacy requirements w.r.t. the vertex degree feature.
This work addresses different settings of the problem allowing edge insertions and/or deletions. We compare different families of integer linear programming formulations of the problem on benchmark social network instances and additionally derive some properties and valid inequalities that we exploit in the solution process.

Keywords

Status: accepted

Back to the list of papers