An increasing volume of data is being collected for research purposes, often containing sensitive information. Leaving out unique identifiers is insufficient to ensure anonymity. One approach to mitigating this risk is to modify the graph structure by adding or deleting edges. Existing heuristic approaches offer speed but limited optimality, while exact methods can achieve better anonymization quality but are computationally expensive. This creates a need for strategies that balance solution quality and efficiency. We propose a method based on simulated annealing that removes edges from the original network structure to achieve
anonymization under two formal privacy models: (n, m)-flavoured k-anonymity, which considers a node’s degree and number of incident triangles, and d-k-anonymity, which is based on the structure up to depth d of a node. Our method aims to balance running time and solution quality while adhering to an edge deletion budget. Experimental results on several real-world social network datasets show that Simulated Annealing can outperform traditional methods in terms of anonymity quality, particularly when higher modification budgets are
allowed. The running time is comparable to that of the baseline methods for smaller and medium-sized graphs but higher for larger graphs.