Study On Privacy Preservation Methods For Relational Data Of Social Networks

Over the past few years, social networks have rapidly increased in popularity, which drastically changed the way people live and communicate in their daily life. However, when many active users heavily relied on some social applications, the privacy protection of their vital information in reality such as attributes and relationships are ignored. Nowadays all kinds of malicious attacks and privacy disclosure have triggered series of serious security threats and social issues. Therefore, it is worthwhile to devote on study of privacy preservation of social networks.Most existing studies of privacy protection in social networks are focused on how to realize various anonymous models based on node attributes or relationships in graphs, while the huge losses of information and computational NP-Hard problem caused by anonymization have been ignored. Moreover, there exists the shortage of network relationship structure are destroyed severely. Due to the absence of extensive discussions on privacy protection of weighted sensitive edges, this thesis improves current k-degree anonymous model, and proposes privacy protecting methods for weighted sensitive edges. The contributions of this dissertation are as follows:(1) To preserve the privacy of un-weighted social networks, an improved privacy protection model is proposed, called SimilarGraph, based on k-degree anonymous graph derived from k-anonymity to keep the network structure stable. Where the main idea of this model is firstly to partition network nodes into optimal number of clusters according to degree sequences based on dynamic programming, and then to reconstruct the network by means of moving edges to achieve k-degree anonymity with internal relations of nodes considered. To differentiate from traditional data disturbing or graph modifying method used by adding and deleting nodes or edges randomly, the superiority of our proposed scheme lies in which neither increases the number of nodes and edges in network, nor breaks the connectivity and relational structures of original network, which has overcome some serious problems such as often incurring large information losses and great structural modifications of original social network after being anonymized. Experimental results show that the model SimilarGraph can not only effectively improve the defense capability against malicious attacks based on node degrees, but also maintain stability of network structure. In addition, the cost of information losses due to anonymity is minimized ideally.(2) In order to protect weighted sensitive edges, a privacy preserving method is proposed to solve this problem, which distinguishes the sensitive and non-sensitive edges according to the edge betweenness centrality that evaluating the importance of entities in network, and then the combined approaches by adding some pseudo-edges and disturbing relationship weights on edges are used to achieve the privacy protection for weighted social network, so that the bottleneck problem of controlling information flow can be well resolved in key area of social network. Experimental results show that the proposed method can not only effectively preserve the sensitive edges with lower computation cost, but also enable the network structures to keep stability, and the capability of defending against malicious attacks for important sensitive edges can be improved greatly.