Performance Analysis of K-Degree Anonymization on Barabási-Albert Graph

Abstract

Anonymity is one the most important problems that emerged with the increasing number of graph-based social networks. It is not straightforward to ensure anonymity by adding or removing some nodes from the graph. Therefore, a more sophisticated approach is required. The consideration of the degree of the nodes in a graph may facilitate having knowledge about specific nodes. To handle this problem, one of the prominent solutions is k-degree anonymization where some nodes involving particular degree values are anonymized by masking its information from the attackers. Our objective is to evaluate the achievement of k-degree anonymization with a well-known graph structure, namely, Barabási-Albert graph, which is similar to the graphs on social networks. Hence, we generate multiple synthetic Barabási-Albert graphs and evaluate the k-degree anonymization performance on these graphs. According to experimental results, the success of k-degree anonymity approximately proportional to the number of edges or nodes.