  Motivated by a strongly growing interest in anonymizing social network data,
we investigate the NP-hard Degree Anonymization problem: given an undirected
graph, the task is to add a minimum number of edges such that the graph becomes
k-anonymous. That is, for each vertex there have to be at least k-1 other
vertices of exactly the same degree. The model of degree anonymization has been
introduced by Liu and Terzi [ACM SIGMOD'08], who also proposed and evaluated a
two-phase heuristic. We present an enhancement of this heuristic, including new
algorithms for each phase which significantly improve on the previously known
theoretical and practical running times. Moreover, our algorithms are optimized
for large-scale social networks and provide upper and lower bounds for the
optimal solution. Notably, on about 26 % of the real-world data we provide
(provably) optimal solutions; whereas in the other cases our upper bounds
significantly improve on known heuristic solutions.
