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, a structure-aware anonymization approach is proposed 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, the approach treats each partitioned substructural component of the network as one single unit to be anonymized. This maximizes utility while enabling anonymization. Since grouping and matching local structures are the essential steps for the anonymization, several alternative grouping and matching techniques are proposed and compared. The proposed methods are applied to both synthetic and real datasets to demonstrate their effectiveness and practical usefulness.