Abstract: In the process of social network data collection and release, privacy information leakage often takes place so that social network privacy protection has aroused people’s concern. In order to solve the problem of significant data loss and poor availability of data in a single mode of social network privacy preserving method ,a k-isomorphism and locally randomized method of privacy preserving is proposed, which included the optimized k-isomorphism method and locally randomized method. The experimental results show that the proposed method in this paper could effectively resist information loss, and has good performance in measurement of harmonic mean of the shortest distance and sub-graph centrality of information within graph. It can protect user’s privacy information effectively and improve the usability of data issued, and also can effectively resist recognition attack from attacker based on background knowledge of graph structure.

Key words: social network, privacy preserving, structure information, k-isomorphism, randomization