K-Degree Anonymization Algorithm In Muti-Graph

Many social networks are released for research and analysis. But at the same time,the data of the social networks may disclose people’s privacy. A social network’s datasetcan be described as a graph. In order to protect privacy, we often publish these graphsafter anonymizing.Most of the thesis only considered the anonymizing of an individual social network.So the anonymization method can not guarantee the privacy when there are severalrelated social networks. In this paper, we propose a method of K-degree anonymizationthat can be used on several related social networks.First, we devise an algorithm about attacking by nodes’ degree sequence. Wheneach of the related graphs is anonymized independently, our algorithm can re-identifythe anonymous nodes.Second, we propose an algorithm to anonymize the1st kind of nodes. The1st kindof nodes are the nodes existing in every graphs. The algorithm make the nodes’ degreesequence in every graphs achieve K-anonymization.Third, we propose an algorithm to anonymize the2nd kind of nodes. The2nd kindof nodes are the nodes only existing in one graph. The algorithm divided the wholedegree sequence of a graph into many sub-sequences, then anonymize eachsub-sequences.Forth, we introduce an algorithm to anonymize the3rd kind of nodes. The3rd kindof nodes are the nodes which not exist in all graphs. The algorithm adjust the nodes’degree sequence to make the3rd kind of nodes seem like the1st kind of nodes. Then,the algorithm in the second part can be used here.Fifth, we extend the algorithm which modify the degree of an individual graph tomuti-graphs. The algorithm will be used when a graph’s anonymous degree sequencecan not construct a graph.In the experiment, we apply our algorithm in two related graphs which are thedataset of real social networks. The experiment show that our algorithm can achieve K-degree anonymization in related graphs. We analyze the change of graph afteranonymizing.