In network science, user privacy is a major concern when handling data such as social networks. These often contain sensitive data on \eg, individuals, companies, and governments. Therefore, it is essential to adequately anonymize this data before sharing or publishing to protect privacy and encourage open science. In this thesis we address this problem by studying k-anonymity in social networks. Specifically, we focus on (n,m)-k-anonymity measure. Building on an existing Integer Linear Program (ILP) encoding that achieves anonymity through edge deletion. We modify this encoding to add edges as well. Additionally, we propose a heuristic to improve the running time and memory usage of the modified ILP. We compare the anonymization settings, adding and deleting edges, on synthetic and real social network datasets, evaluating their running time, memory usage, and solution quality. This analysis provides insights into the trade-off between the two settings.