Research On Anonymity Models And Algorithms For Social Network With Sensitive Relationship

The technical progress of Web prompts the development of social networks, such as facebook(facebook.com), twitter(twitter.com), myspace(myspace.com), hi5(hi5.com). Social networks bring much convenient to people’s communication. However, social network contains much privacy information, whose publishing and sharing would threat individuals’privacy. Therefore, research on privacy preservation on social network publishing or sharing has important practical significance.Among the various privacy-preservation techniques, anonymity has become one of the most popular methods for its security and effectivity. The main idea of anonymity is to modify the original social network to protect individuals’privacy in social networks. Existing privacy preservation methods for social networks focus on protecting individual, which cannot protect sensitive relationship in social network effectively. This thesis mainly concentrates on the research of anonymity models and anonymization algorithms for privacy-preserving social networks with sensitive relationship. The contributions of the thesis are as follows:(1) An l-sensitive edge anonymity model is proposed, which can protect sensitive relationship in social networks with sensitive relationship effectively. The existing methods prevent the disclosure of the sensitive relationship by deleting the sensitive relationship in social network, which distort the social network greatly, and make the utility of the anonymized social networks low. Thus, we propose the l-sensitive edge anonymity model. The model ensures that if a node has a sensitive edge, the number of the sensitive edges of the node is at least lto make the probability of the attacker exactly identifying sensitive relationship is less than1/l, which can protect the privacy of individuals. The experiments show that l-sensitive edge anonymity model can retain more utility of the social network than the method of deleting sensitive edges under the condition of preserving the sensitive relationship. (2) A (k,l)-anonymity model is proposed, which adds degree anonymization constraint on l-sensitive edge anonymity model. So it can resist degree attack, at the same time preserve sensitive edge. The existing (k,2)-anonymity model can prevent neighborhood attack, but it cannot capture degree attack. Thus we proposes the (k, l)-anonymity model, which requires that the number of the sensitive edges of a node with sensitive edge is at least l, and that there exist at least k nodes with the same degree. So it not only protects sensitive relationship, but also resists degree attack. The thesis also proposes a k-degree sequence construction algorithm based on k-degree sequence to implement the (k,l)-anonymity model. Experimental results show that the model can protect sensitive relationship in social networks effectively.(3) A (k, l, m)-anonymity model is proposed, which can protect sensitive attribute and sensitive relationship in social networks effectively. The existing anonymity models cannot protect sensitive information in nodes’attributes. Therefore, the thesis proposes the (k,l, m)-anonymity model, which adds the revealing constraints on sensitive attributes based on (k,l)-anonymity model. The proposed model requests that the sensitive attribute values in its corresponding equivalence class satified (k,l)-anonymity meet the need of m-diversity constraint. This thesis also proposes a (k, l,m)-clustering algorithm based on weighted hierarchies distances. Experimental results show that (k,l, m)-anonymity model can protect sensitive attributes and sensitive relationships in social networks with sensitive relationship and nodes attributes.