Time-efficient algorithm on degree anonymization by combination of vertex and edge addition

摘要

In previous work about privacy preservation of graph modeled network, k-degree-anonymization has been a well-developed subject. We studied various researches on both edge addition and vertex addition. In many algorithms, the edge addition is a heuristic process, which may bring in some extra time cost. Interested in the problem, we introduce the idea of vertex addition, and develop a framework that combines edge addition and vertex addition. We use a greedy idea to add edges in the original graph, and use as least pseudo vertices as possible to produce a k-degree-anonymous graph. The time efficiency of our approach lies on the nature of greed edge addition.