Article Preview
Top
Backstrom et al. (2007), one of the pioneering works on graph anonymization, point out shortcomings of naive graph anonymization, which replaces identity of individuals by synthetic identifiers. Attackers are able to identify their target from remarkable existing (passive attacks) or created (active attacks) structural local properties of the graph.
To prevent such attacks, various anonymization methods are proposed that further modify the graph in order to hide remarkable structural features.
Liu and Terzi (2008) propose to anonymize graphs by inserting new edges in order to make the degree of each vertex undistinguishable from that of, at least, k-1 other vertices. Attacks based on degree information can be prevented. The graph is said to be k-degree-anonymous after modification. Zhang et al. (2009) propose to swap and delete edges based on degree information in order to prevent re-identification of sensitive edges in simple graph. Ying and Wu (2008) suggest randomized edge addition, deletion and switching to anonymize graph while controlling the effect on graph spectrum.
Zou, Chen, and Ozsu (2009) and Cheng, Fu, and Liu (2010) try and prevent a broader range of structural attacks by proposing a graph modification approach that involve vertices and edges insertion and create homomorphic (thus undistinguishable) components. Similarly, Wu, Xiao, Wang, He, and Wang (2010) propose a k-symmetry model to prevent re-identification via any structural attacks.
Considering labels of vertices in addition to the basic structural information, Zhou and Pei (2008) propose to extract the neighborhoods of all vertices, group vertices and anonymize the neighborhoods of vertices in the same group by generalizing vertex labels and adding edges.