EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

4243. (k,l)-anonymity of networks via their k-metric antidimension

Invited abstract in session WD-29: Optimization issues on graphs II (Contributed), stream Combinatorial Optimization.

Wednesday, 14:30-16:00
Room: 157 (building: 208)

Authors (first author is the speaker)

1. Manuel Munoz-Marquez
Statistics and Operations Research, Cadiz University
2. Elena Fernandez
Statistics and Operations Research, University of Cadiz
3. Dorota Kuziak
University of Cadiz
4. Ismael González-Yero
University of Cadiz

Abstract

This work focuses on the (k,l)-anonymity of some networks as a measure of their privacy against active attacks.
Two different types of networks are considered. The first one consists of graphs with a predetermined structure, namely cylinders, toruses, and 2-dimensional Hamming graphs, whereas the second one is formed by randomly generated graphs. In order to evaluate the (k,l)-anonymity of the considered graphs, we have computed their k-metric antidimension. To this end, we have taken a combinatorial approach for the graphs with a predetermined structure, whereas for randomly generated graphs we have developed an integer programming formulation and computationally tested its implementation. The results of the combinatorial approach, as well as those from the implementations indicate that, according to the (k,l)-anonymity measure, only the 2-dimensional Hamming graphs and some general random dense graphs are achieving some higher privacy properties.

The main contributions of this research are the following:
1. Some theoretical results concerning cylinders, toruses and Hamming graphs are given.
2. We have developed an integer programming formulation for finding the k-metric antidimension of a given graph G. The formulation can be used as a tool to deal with randomly generated graphs as well as with classes of graphs for which their k-metric antidimension is not known theoretically.

Extensions of these results to multiset distances are currently under development.

Keywords

Status: accepted

Back to the list of papers