Social networks are getting more and more attention in recent years. People join social networks to share their information with others. However, due to the different cultures and backgrounds, people have different requirements on what kind of information should be published. Currently, when social network websites publish data, they just leave the information that a user feels sensitive blank. This is not enough due to the existence of the label-structure relationship. A group of analyzing algorithms can be used to learn the blank information with high accuracy. In this paper, we propose a personalized model to protect private information in social networks. Specifically, we break the label-structure association by slightly changing the edges in some users’ neighborhoods. More importantly, in order to increase the usability of the published graph, we also preserve the influence value of each user during the privacy protection. We verify the effectiveness of our methods through extensive experiments. The results show that the proposed methods can protect sensitive labels against learning algorithms and at the same time, preserve certain graph utilities.