Abstract
Graph structured data can be ubiquitously found in the real world. For example, social networks can easily be represented as graphs where the graph connotes the complex sets of relationships between members of social systems. While their analysis could be beneficial in many aspects, publishing certain types of social networks raises significant privacy concerns. This brings the problem of graph anonymization into sharp focus. Unlike relational data, the true information in graph structured data is encoded within the structure and graph properties. Motivated by this, we propose a structure aware anonymization approach that maximally preserves the structure of the original network as well as its structural properties while anonymizing it. Instead of anonymizing each node one by one independently, our approach treats each partitioned substructural component of the network as one single unit to be anonymized. This maximizes utility while enabling anonymization. We apply our method to both synthetic and real datasets and demonstrate its effectiveness and practical usefulness.