Tongxin xuebao (Jun 2016)
Method of constructing an anonymous graph based on information loss estimation
Abstract
A potential attack based on degree information by re-identifying target vertexes from a sequence of published graphs was analyzed.To deal with this kind of attack,a k-anonymous graph stream constructing method based on information loss estimation was provided.Information loss caused by re-constructing graph was controlled by using the method of attributes generalization of nodes and the structure generalization of sub-graph.The disturbance in sub-graph was forbidden to prevent the attack.The method of measuring the information loss of nodes and structures during the anonymous process due to re-construction of graph was defined.A k-anonymity cluster algorithm based on greedy clustering algorithm was build,which realized anonymous partition according to the information loss.Finally,a method of constructing anonymous social network for the evolving social network with the least information loss was provided.The experiments on medical diagnostic data set show that the algorithm of constructing anonymous graph based on the information loss estimation can be used to control the loss of information.
