# 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. privacy preserving; k-degree anonymity; social network; graph; utility +
Footnote †: journal:  
1 FSOpt_k: Finding the Optimal Anonymization Level for a Social Network Graph  
M.N. ; [PERSON], [PERSON]; [PERSON]. There are some models for anonymizing social network graphs. One of these models is k-degree anonymity, which protects the graph from attacking the degree of nodes. In this model, it is guaranteed that for each node in the graph, there are at least k-1 nodes with the same degree. Different algorithms were applied to the social network graph to apply this model. All of these algorithms provide the required privacy level (k parameter value in the k-degree anonymity model) in the graph. They also maintain the utility of the graph for analyzing data in the social network graph. However, the value of parameter k must be given to these algorithms as input. The data owner may not be able to determine this value in advance. In fact, the data owner may only be aware of the desired amount of information loss for their social network. In addition, the value of parameter k is determined regardless of the characteristics of the social network graph. As such, a k value may be appropriate for one graph while not good for another graph. In other words, a k value for one graph may have a high level of information loss, but the same k value for another graph may not have much information. Therefore, finding the optimal value of k for a social network graph is an important issue that has not been considered in algorithms so far. To this end, in this paper, we present a method based on the NaFa [5] algorithm that can find the best k value based on the properties of the graph degree sequence and anonymize the graph accordingly. In this method, the maximum amount of k that can be applied to the social network graph so that the social network graph has the desired utility defined by the data owner is determined by the NaFa algorithm. Since the graph modification technique is widely used to preserve graph privacy, this paper focuses on this technique to anonymize the graph. The purpose of this paper is to introduce a new challenge and propose a solution for it. This challenge is to find the amount of privacy level, or in other words, the amount of graph anonymization, in the k-degree anonymity model according to the characteristics of the graph. In this way, without giving the value of k as an input to the algorithm, as in the previous algorithms, the graph becomes anonymous in such a way that the amount of anonymity applied to the graph is proportional to its characteristics and different from other graphs. In addition, to address this challenge, the algorithm proposed in this paper maintains the utility of the anonymous graph at an acceptable level. The rest of this paper is organized as follows. Section 2 describes some of the related works carried out on graph anonymization.