Announcement: Denisa Arsene will present our work at Complex Networks

On 9 December 2025, my student Denisa Arsene will present our work on social network anonymisation at the 14th International Conference on Complex Networks and their Applications, held in Binghamton, New York, USA!

The idea

Social scientists produce social network data. In order to share that data with other scientists, they must ensure that the identity of the actual people in the networks is protected. Simple pseudonymisation is typically not enough, because the neighbourhoods of individuals (nodes) in the network (i.e., what their friend group looks like) can be so unique as to leak information about their identity. After all, a lot of online social networking sites allow users to query details about other users’ connections on the social networking site.

Hence, some form of anonymisation is needed before social network data can be shared. This network anonymisation process typically consists of making subtle changes to the network to ensure that no individual has unique features. This particular criterion is called 2-anonymity, meaning that for each node, there exists at least one other node (and hence: person) with the same exact features.

In our work, we focus edge deletion: given a budget of a number of edge deletions, we try to remove those edges that maximise the number of nodes that are 2-anonymous w.r.t. features that characterise how many connections each node has (the number of friends of the person represented by the node), and how many incident triangles the node has (how many friend relationships there are between friends of the person). This particular measure strikes a good balance between other popular measures that are either very expensive to compute, or too trivial to be a real threat.

In our approach, we choose for simulated annealing; a metaheuristic that uses stochastic search to first focus on exploring the search space, and then gradually shifts its focus to exploiting promising areas. We call our approach SANA (Simulated Annealing for Network Anonymisation). Our findings indicate that SANA tends to achieve better anonymisation (up to 18$times$ more $2$-anonymous nodes) than other heuristic algorithms with similar running times. When looking at other quality measures, related to how well the algorithm preserves key network properties, we find that SANA performs comparably to the SotA.

The collaboration

A year and a half or so ago, two of my former colleagues from Leiden University, dr. Frank F. Takes and Rachel G. De Jong, and I decided to explore collaborations on the topic of social network anonymisation. After all, I had been working on uniquely identifying nodes in networks (LSM2023, LSB+2024), so it seemed only natural to me that I could apply the tricks that I used in that work to the opposite problem.

That turned out to be somewhat optimistic, but we decided to explore this topic further anyway, and I wrote a proposal for a BSc thesis project to explore network anonymisation, with Frank and Rachel as external advisors.

Denisa and four fellow students chose/were assigned to (it’s complicated) that project, and we spent 10 weeks exploring the topic from different angles. You can find posters that summarise their projects on this website (Ctrl+F for “Network anonymization for science”). Frank, Rachel, Denisa and I ended up turning Denisa’s project into a research paper, and submitted it to the Complex Networks conference.

Denisa’s poster

The paper was accepted, so Denisa will travel to Binghamton, New York, USA to present our work to the community during a poster presentation! Many thanks to all of my (former) students who gave feedback on her poster and her pitch!

Acknowledgements

We thank Denisa’s team mates, Andrei Ioniţă, Jakub Matyja, Mike J.J.S. Erkemeij, and Emke de Groot for their constructive feedback and discussions. We also thank the anonymous reviewers for their valuable comments that helped us improve the manuscript. Finally, we thank the TU Delft University Fund that, through their FAST programme has funded part of Denisa’s trip to the USA.