Graph Based Privacy-preserving Schemes In Mobile Social Network Data Publication

Mobile social network,a social network built on mobile communication network,supports mobile social media such as We Chat,Weibo,Facebook,etc.Thanks to it,people can interact with each other on various social APPs anytime and anywhere.With the increasing development of mobile social networks,these social APPs gen-erate a large amount of data.These data are released to third parties,and widely used in various fields such as product recommendation,disease detection,and sci-entific research,thus creating huge economic and social value.However,as these data contain a variety of users’privacy information,there will be a matter of pri-vacy leakage once they are directly published.Although network operators initially anonymize the data before publishing them,attackers can still extract users’social attributes,explore their social relationships and figure out their identities based on their social relationship topology.Therefore,how to design an effective anonymous mechanism to protect users’privacy has become one of the most important issues in mobile social network graph data publishing.This thesis first gives a comprehensive overview of such issues in publishing mobile social network graph data as the privacy problem,attack models and main-stream privacy protection technologies,and then proposes different privacy protec-tion strategies for users’privacy leakage caused by different attack models.The main work of this paper is as follows:First,to solve the problem of identity privacy leakage caused by 1-neighborhood graph attacks,a privacy-preserving scheme based on graph partition is proposed.This scheme employs κ-neighborhood anonymous model and involves two steps:node clustering and graph modification.In order to improve the precision of node clustering,the scheme proposes spectral clustering algorithm on the basis of Ratio-cut,which can divide nodes into several clusters of approximately equal size.In this algorithm,the concept of degree based graph entropy is introduced to characterize the degree heterogeneity.In the process of graph modification,an algorithm based on bipartite graph matching is proposed to retain more structure information of the graph so as to obtain perfect matches between nodes,and keep the 1-neighborhood graphs isomorphic in the same cluster by modifying the graph structure according to the matching results.Theoretical analysis shows that the scheme can effectively resist the de-anonymous attack of 1-neighborhood graph.Experimental analysis proves that the scheme has high data utility.Second,to solve the problem of user identity privacy leakage caused by 1~*-neighborhood attacks,this paper proposes a identity privacy-preserving scheme based on graph edit distance.In this scheme,theκ-neighborhood anonymous model is also employed to protect users’identity privacy.Besides,to better measure the similarity of the 1~*-neighborhood graph,the concept of gap-degree is proposed in addition to the metrics of degree,in-degree,and out-degree.And then,on the basis of these metrics,a structural feature matrix is constructed to calculate the similarity between nodes with J-S divergence,thus improving the accuracy of node cluster-ing.What’s more,in order to reduce the total cost of graph modification,a graph modification algorithm based on graph editing distance is proposed.This algorith-m utilizes a seed graph matching algorithm to simply and effectively calculate the graph edit distance,find the optimal graph edit path,and modify the graph struc-ture accordingly.Theoretical analysis shows that the scheme can effectively resist the de-anonymous attacks based on the 1~*-neighborhood graph.The experimental analysis proves that the scheme has high data utility while ensuring user privacy.Third,to solve the problem of identity privacy leakage caused by degree attack on mobile social network users,this thesis proposes an identity privacy-preserving scheme based on graph reconstruction under the differential privacy model.In order to reduce the sensitivity and retain the structure information of the graph as much as possible,this scheme introduces a degree projection method based on curve fit-ting to limit the maximum degree in the graph and retain important edges as much as possible.In order to reduce the increasing amount of noise,the scheme uses an improved fuzzy-clustering algorithm to cluster the nodes,and realizes personal-ized differential privacy according to the degree variance of each cluster,inspired by the idea of local differential privacy.In order to make the reconstructed graph have higher data utility,the scheme reconstructs the graph by using connected dom-inating set to construct backbone network,which effectively retains the structural characteristics of the original graph.The analysis shows that the scheme not only satisfies the needs of differential privacy,but also has high data utility.Finally,to solve the problem of identity and relationship privacy leakage caused by subgraph attacks in mobile social networks,this thesis proposes a privacy-preserving scheme based on link prediction under the uncertainty graph model.This scheme proposes a new two-layer mobile social network model:user relationship topology layer and user attribute layer,which are represented by user relationship topology graph and attribute similarity graph respectively.The attribute layer of n-odes is modeled as a hypercube with weighted(N,q)-hypercube,and the edge weight represents the similarity of attributes between nodes.The probability of edge con-nection between nodes in the attribute graph is calculated according to the disjoint paths between nodes.In the user relationship topology graph,in order to protect the identity privacy of users,noise satisfying Laplacian distribution is added to the degree of nodes,and Chung-Lu random graph model is used to convert it into a probability graph.Based on the two-layer model,the link between nodes is predict-ed.The predicted probability edge is added to the probability graph as uncertainty,and thus resulting in the final anonymous graph.Theoretical analysis shows that the scheme can resist subgraph attacks.The experimental analysis proves that the scheme has high data utility and can well maintain the graph structure information.In conclusion,this thesis proposes corresponding privacy protection methods for the privacy leakage problem caused by different attack models.These methods can not only resist different de-anonymous attacks and protect users’privacy,but also ensure the graph data utility.