FSopt_k: Finding the Optimal Anonymization Level for a Social Network Graph

Abstract

k-degree anonymity is known as one of the best models for anonymizing social network graphs. Although recent works have tried to address the privacy challenges of social network graphs, privacy levels are considered to be independent of the features of the graph degree sequence. In other words, the optimal value of k is not considered for the graph, leading to increasing information loss. Additionally, the graph may not need a high privacy level. In addition, determining the optimal value of k for the graph in advance is a big problem for the data owner. Therefore, in this paper, we present a technique named FSopt_k that is able to find the optimal value of k for each social network graph. This algorithm uses an efficient technique to partition the graph nodes to choose the best k value. It considers the graph structure features to determine the best privacy level. In this way, there will be a balance between privacy and loss in the anonymized graph. Furthermore, information loss will be as low as possible. The evaluation results depict that this algorithm can find the optimal value of k in a short time as well as preserve the graph’s utility.

Keywords

• privacy preserving
• k-degree anonymity
• social network
• graph
• utility