Abstract: Serious concerns on privacy protection in social networks have been raised in recent years. When an adversary uses some types of background knowledge to conduct an attack, an individual's privacy may be threatened. In pioneer work, node disclosure and edge disclosure were studied. However, there is little effort to deal with sensitivity disclosure. To address it, sensitivity disclosure was formally defined and theoretically analyzed. Taking into account all these disclo- sures, three level privacy protection was proposed, and lts graph was presented as the solution. ho generate Its graph,Its algorithm is both theoretically correct and experimentally effective.

Key words: Data publishing, Social networks, Three level privacy protection, Sensitivity disclosure