On the $(k,\ell)$-multiset anonymity measure for social graphs
Preprint
Abstract
The publication of social graphs must be preceded by a rigorous analysis of privacy threats against social graph users. When the threat comes from inside the social network itself, the threat is called an active attack, and the de-facto privacy measure used to quantify the resistance to such an attack is the $(k,\ell)$-anonymity. The original formulation of $(k,\ell)$-anonymity represents the adversary's knowledge as a vector of distances to the set of attacker nodes. In this article, we argue that such adversary is too strong when it comes to counteracting active attacks. We, instead, propose a new formulation where the adversary's knowledge is the multiset of distances to the set of attacker nodes. The goal of this article is to study the $(k,\ell)$-multiset anonymity from a graph theoretical point of view, while establishing its relationship to $(k,\ell)$-anonymity in one hand, and considering the $k$-multiset antiresolving sets as its theoretical frame, in a second one. That is, we prove properties of some graph families in relation to whether they contain a set of attacker nodes that breaks the $(k,\ell)$-multiset anonymity. From a practical point of view, we develop a linear programming formulation of the $k$-multiset antiresolving sets that allows us to calculate the resistance of social graphs against active attacks. This is useful for analysts who wish to know the level of privacy offered by a graph.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- On the $(k,\ell )$-anonymity of networks via their k-metric antidimensionScientific Reports, 2023
- Preventing active re-identification attacks on social graphs via sybil subgraph obfuscationKnowledge and Information Systems, 2022
- Distance-based vertex identification in graphs: The outer multiset dimensionApplied Mathematics and Computation, 2019
- On the computational complexities of three problems related to a privacy measure for large networks under active attackTheoretical Computer Science, 2019
- Robust active attacks on social graphsData Mining and Knowledge Discovery, 2019
- On analyzing and evaluating privacy measures for social networks under active attackInformation Sciences, 2019
- Conditional adjacency anonymity in social graphs under active attacksKnowledge and Information Systems, 2018
- Complexity of metric dimension on planar graphsJournal of Computer and System Sciences, 2017
- Characterizing 1-Metric Antidimensional Trees and Unicyclic GraphsThe Computer Journal, 2016
- Protecting respondents identities in microdata releaseIEEE Transactions on Knowledge and Data Engineering, 2001