The first necessary anonymization technique in both the contexts of micro- and network data consists in removing identification. This nave technique has quickly been recognized as failing to protect privacy. For microdata, Sweeney et al. propose k-anonymity to circumvent possible identity disclosure in naively anonymized microdata. `-diversity is proposed in order to further prevent attribute disclosure. Similarly for network data, show that naive anonymization is insu_cient as the structure of the released graph may reveal the identity of the individuals corresponding to the nodes. This problem and quantify the risk of re-identification by adversaries with external information that is formalized into structural queries. Recognizing the problem, several works propose techniques that can be applied to the naive anonymized graph, further modifying the graph in order to provide certain privacy guarantee. Some works are based on graph models other than simple graph . To our knowledge, the first to consider modeling social networks as labeled graphs, similarly to what we consider in this paper. To prevent re-identification attacks by adversaries with immediate neighborhood structural knowledge, propose a method that groups nodes and anonymizes the neighborhoods of nodes in the same group by generalizing node labels and adding edges. They enforce a k-anonymity privacy constraint on the graph, each node of which is guaranteed to have the same immediate neighborhood structure with other nodes. In they improve the privacy guarantee provided by k-anonymity with the idea of `-diversity, to protect labels on nodes as well. Try to be more practical by considering users’ different privacy concerns. They divide privacy requirements into three levels, and suggest methods to generalize labels and modify structure corresponding to every privacy demand.