Privacy Preserving Of Social Network Based On Vertex Addition

Recently, due to the combination of Internet and social network. A lot of online social network services are coming to our life, such as Weixin, Renren, Weibo etc. Quantity of data are created from the using of social network services, these social network data always contain much private information of social network users, so directly or naivedly anonymized publication of the data will lead to severe privacy disclosure problem. Privacy preserving operations should done before publishing of social network data in order to provide protection of privacy of social actors. However, most of existing approaches only focus on providing privacy protection, the utility of the published social network is severely distorted. At the same time, most of the approaches achieve anonymization through add edges into the social network, and vertex addition method is rarely considered by the researchers.In this paper, we firstly introduced the procedure of social network privacy protection, including the privacy in the social network, graph data model of published social network, background knowledge of adversary, privacy attacks from adversary, privacy disclosure and the utility of the published social network. Understanding the procedure helped us to choose what we can do and how we can propose social network anonymization approach.Based on the shortcomings of existing approaches and the understanding procedure of social network anonymization, we choose to handle two very important problems in the field of social network privacy protection.1) As to the identity disclosure problem in simple undirected social network, when the adversary has the degree information as background knowledge, we selected the K-degree model to guarantee the privacy of social network data. At the same time, we introduced the community structure and path length between vertices in the process of anonymization. So when selecting candidate vertices to increase the degree of target vertex, the "nearest" vertices has the highest priority, therefore when adding edges and vertices to make the graph K-degree anonymous, the utility of the social network can be well preserved.2) When the adversary has degree information as background knowledge, and want the get the sensitive attribute information of the victim in a vertex-attributed undirected social network, we choose to achieve K-degree L-diversity through adding vertices into the social network. Instead of generalizing the sensitive attributes of vertices, we leave the attributes unchanged, which preserves the utility of the social network utility.We used the transitivity, average clustering coefficient and average path length to varify that the utility of the anonymized social network produced by our two approaches is well preserved. We do experiments on five social networks, namely ca-HepTh, email-Enron, ca-CondMat, ca-AstroPh and ca-GrQc, for the approach tackling identity disclosure problem. For the approach with attribute disclosure problem, we use the Adult to form the sensitive attribute of vertex in the social network, which is very popular in the field of machine learning. And used the method proviced by networkx to form the network structure, we generated three different social network structures, namely scale-free social network, small world social network, random social network. All the experiments demonstrated the superiority of our proposed approaches.