Utility-aware Social Network Anonymization using Genetic Algorithms CCS: Security and privacy Data anonymization and sanitization CCS: Computing methodologies Genetic algorithms

Samuel Bonello, Rachel G. de Jong, Thomas H. W. Bäck and Frank W. Takes · 2025

Read Utility-aware Social Network Anonymization using Genetic Algorithms CCS: Security and privacy Data anonymization and sanitization CCS: Computing methodologies Genetic algorithms by Samuel Bonello, Rachel G. de Jong, Thomas H. W. Bäck and Frank W. Takes (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-05183.txt.

Introduction

Sharing a social network data set can expose facts about real people, so names alone are not the only risk. Samuel Bonello and co-authors, in a 2025 paper, tackle a graph where a person can be picked out by the shape of the links around them. Their aim is to hide more of those shapes while keeping the data useful for later study.

The team built two versions of a search method that breeds and tests small changes to a graph. One version steers its changes toward links that still leave a person exposed. On real network data sets, the method hid about fourteen times more nodes than the best older method. It also kept task scores level while cutting fewer links, which makes the shared data safer and still worth using.

Catalog record

CREATORSamuel Bonello, Rachel G. de Jong, Thomas H. W. Bäck and Frank W. Takes
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-05183

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Utility-aware Social Network Anonymization using Genetic Algorithms CCS: Security and privacy Data anonymization and sanitization CCS: Computing methodologies Genetic algorithms Samuel Bonello, Rachel G. de Jong, Thomas H. W. Bäck and Frank W. Takes Abstract . Social networks may contain privacy-sensitive information about individuals. The objective of the network anonymization problem is to alter a given social network dataset such that the number of anonymous nodes in the social graph is maximized. Here, a node is anonymous if it does not have a unique surrounding network structure. At the same time, the aim is to ensure data utility, i.e., preserve topological network properties and retain good performance on downstream network analysis tasks. We propose two versions of a genetic algorithm tailored to this problem: one generic GA and a uniqueness-aware GA (UGA). The latter aims to target edges more effectively during mutation by avoiding edges connected to already anonymous nodes. After hyperparameter tuning, we compare the two GAs against two existing baseline algorithms on several real-world network datasets. Results show that the proposed genetic algorithms manage to anonymize on average 14 times more nodes than the best baseline algorithm. Additionally, data utility experiments demonstrate how the UGA requires fewer edge deletions, and how our GAs and the baselines retain performance on downstream tasks equally well. Overall, our results suggest that genetic algorithms are a promising approach for finding solutions to the network anonymization problem. 1. Introduction In the field of network science or social network analysis, real-world social network data is frequently used, for example to model networked processes such as influence maximization ( Li et al. 2018 ) or epidemic spread ( Azizi et al. 2020 ) . Here, the social network data is a graph in which the nodes are people, and edges represent meaningful connections such as friendship or human communication. Network data is typically the input of downstream network analysis tasks and algorithms, such as assessing network robustness ( Albert et al. 2000 ) , finding central nodes ( Saxena and Iyengar 2020 ) and community detection ( Blondel et al. 2008 ) . In light of open science, social network data would ideally always be openly accessible. However, in many situations, a social network contains personally identifiable information that upon disclosure would violate people’s privacy. Various more generic approaches for minimizing above mentioned disclosure risk have been introduced in literature, for which the focus was initially on more traditional tabular data ( Hundepool et al. 2012 ; Sweeney 2002 ; Dwork 2008 ) . However, network data introduces new challenges and requires different approaches as the network structure surrounding a node can itself be used to identify individuals ( Backstrom et al. 2007 ; Romanini et al. 2021 ; de Jong et al. 2024b ) . Existing research to mitigate this problem can roughly be categorized into three streams of work, concretely being differential privacy ( Sala et al. 2011 ; Proserpio et al. 2014 ; Wang and Wu 2013 ) , clustering methods ( Campan and Truta 2009 ; Bhagat et al. 2009 ; Liu and Mittal 2016 ; Minello et al. 2020 ) and approaches based on k -anonymity ( Liu and Terzi 2008 ; Hay et al. 2008 ; Romanini et al. 2021 ; Zou et al. 2009 ) . We briefly discuss all three below. In differential privacy, the user does not get access to the complete dataset, but instead is allowed to query parts of the data. Privacy is then guaranteed by adding noise to query answers in such a way that the presence or absence of an individual can not be derived. Some network-specific differential privacy approaches focus on answering a single query ( Proserpio et al. 2014 ; Hay et al. 2010 ) , while others generate a graph based on the answer produced, such as the joint degree distribution ( Sala et al. 2011 ; Wang and Wu 2013 ; Xiao et al. 2014 ) . In the second category of approaches based on clustering, privacy is ensured by creating a new network in which nodes are grouped together into large enough supernodes that no longer reveal the identity of the nodes contained in it. A drawback of these two categories of approaches is that either a user is limited by which queries can be asked, or certain graph properties are substantially distorted. For example, in differential privacy communities are not guaranteed to be preserved, as the network is generated from a global distorted joint degree distribution. More generally, these approaches often lead to a loss or even impossibility of measuring data utility , i.e., the extent to which topological properties of the network are preserved, and performance on downstream tasks is retained. Additionally, in many fields of applied research, such as the social sciences, it must be possible to publish the network dataset underlying an analysis for reasons of reproducibility. Therefore, in this paper we focus on the third category, being k -anonymity, as this approach ultimately enables publication of (parts of) a k -anonymized version of the network. A node is said to be k -anonymous if it is equivalent to at least k-1 other nodes. In this paper, we focus on the scenario in which a node is anonymous if it is not unique, i.e., k=2 . The criteria for two nodes to be equivalent, depends on the chosen anonymity measure. This measure essentially represents the attacker scenario, i.e., what information is in the hands of a potential adversary aiming to deanonymize the network. In the version of the network anonymization problem considered in this paper, the aim is to maximize the number of 2-anonymous nodes with a limited number of alterations to the graph. Based on the chosen anonymity measure the difficulty of anonymizing a network in terms of computational complexity differs. For example, when using the degree of a node as anonymity measure, the problem can be solved in \mathcal{O}(n^{2}) time, where n is the number of nodes ( Liu and Terzi 2008 ) . However, when the measure takes into account the exact graph structure surrounding a node, this problem is NP-hard ( Zhou and Pei 2008 ) , requiring approximation algorithms to handle larger graph inputs. The anonymization problem is not monotonic ( de Jong et al. 2024a ) , implying that more alterations do not always result in higher anonymity. Moreover, the anonymization problem is clearly an example of an optimization problem with a tremendously large search space, as a subset of all edges should be selected for modification in order to maximize the number of anonymous nodes. Hence, a genetic algorithm is a logical candidate for the anonymity maximization problem. Moreover, GAs have proven to be effective in other problems where the input is a (social) network ( Lotf et al. 2022 ; Azaouzi et al. 2019 ; Caschera et al. 2019 ) . In this paper, we first introduce a generic genetic algorithm (GA) tailed to the network anonymization problem. An individual in the population is a bitstring of length m , where m is the number of edges in the network, and mutation from 0 to 1 indicates that in the solution, this edge is deleted

Read the complete text