Supervisors:

Abstract. Due to the large interest in analyzing social network structures for scientific and market researches, the anonymization of data sets is of large interest in recent research. Given a simple graph G, the NP-hard k-degree anonymization problem asks for a supergraph G ′ with a minimum amount of edge additions, such that each vertex degree occurs at least k times. Focusing power law distributed social network graphs, we present various polynomial-time heuristics for k-degree anonymization, based on the dynamic program-ming algorithm of Liu and Terzi. All the graph degree anonymization heuris-tics work in two phases: Phase 1 is to compute and k-anonymize the degree sequence of the input graph. In Phase 2, the k-anonymous degree sequence is realized as a supergraph of the input graph. While the heuristic of Liu and Terzi has been shown to be optimal if the solution is very large, we examine its usability for rather small real-world instances. As we were not able to k-anonymize any of the degree sequences of the social network graphs used within this work such that realization is possible in Phase 2, we modified the algorithm of Liu and Terzi in an algorithm engineering process in several steps. Furthermore, we introduce several degree sequence realization heuris-tics which solve Phase 2 of the graph anonymization process and compare these heuristics regarding to effectiveness and running-time. Using these al-gorithms, we were able to optimally k-degree-anonymize many large social network graphs with> 100.000 vertices and k = 200 in less than an hour. Abstrakt. Datensätze sozialer Netzwerke sind als Quelle wissenschaftlicher Forschungen sowie Marktforschungen von großer Bedeutung. Um die Pri