# FSOpt_k: Finding the Optimal Anonymization Level for a Social Network Graph
## 2 Related Work
#### Graph Modification Techniques  
Modification techniques are based on the graph structure to achieve anonymity. They modify the structure of the graph so that an adversary cannot discover some information about users in the graph. It is conducted by changing the vertices and the edges of the graph, as shown in Figure 1. One of the popular models in this category is k-anonymity [8; 9]. In this model, the probability of identifying an individual in the dataset is constrained to 1/k. This model can be applied to several characteristics of a social network graph. As an example, consider the degree sequence of a graph. In this example, the degree sequence satisfies k-anonymity if there are at least k vertices with the same degree. In 2007, [PERSON] and [PERSON] used edge addition and deletion to make the graph k-degree anonymous [10]. This method was designed to prevent identity and link disclosure. Some works on k-anonymity considered k-neighborhood sub-graphs and tried to make them k-anonymous. [PERSON] [11] made an effort to anonymize the graph in such a way that for each vertex, there are at least k-1 other vertices with the same 1-neighborhood. They used a greedy method to anonymize the labels of vertices. This method adds fake edges to obscure nodes according to their k-neighborhood. The number of vertices in the graph remained unchanged. They also put under consideration attribute disclosure. [PERSON] et al. [12] considered the local structures of nodes so that after anonymization, the anonymous graph has a structure similar to the original graph. In spite of having a higher  
Figure 1: Categorization of the privacy-preserving graph publishing techniques. privacy level, this algorithm has high complexity. Therefore, it cannot be employed to anonymize large graphs. [PERSON] [13] showed that their algorithm does not work when the adversary knows some information about the vertices at a distance of two or higher from a vertex. Therefore, they proposed an algorithm to handle this situation. Another type of k-anonymity is k-candidate anonymity [14]. A vertex is k-candidate anonymous if there are at least k-1 vertices with the same answer according to a question Q. k-automorphism is an alternative k-anonymity method [15]. A graph has k-automorphism if there are two conditions: the first one is existing k-1 automorphic functions Fa (a = 1,..., k-1) in graph G and the second one is that for each vertex vi in graph G, Fa1(vi) \(\
eq\) Fa2(vi) (1 \(<\) a1 \(\
eq\) a2 \(<\) a-1). Finding an appropriate automorphic function is an important issue. Therefore, they used three methods to identify this function: graph partitioning, block alignment, and edge copy. Then, they presented a k-automorphic algorithm which is based on these three methods. Contrary to having a high privacy level, this algorithm has greater complexity than the previous works. Therefore, it is not suitable for large networks. K2-anonymity [16] is another approach that has the purpose of preventing friendship attacks. In a friendship attack, the adversary can detect the victim by checking the degrees of end nodes of the edges in the graph. Therefore, in order to hinder this attack, there should be at least k-1 vertices with the same degrees of the end nodes of the edges incident to a special vertex. They also proposed a heuristic method to anonymize larger networks. K-core attacks [17] violate the user's privacy according to the coreness of the vertices and their degrees in the graph. To deal with this attack, the authors presented a (k, d)-core anonymity technique that anonymizes the vertices based on their k-core characteristics. It applies edge and vertex addition to modify the graph. On the contrary to the usefulness of the k-anonymity model, it cannot guarantee the privacy of the graph in the case where an attacker knows additional information about the user. Therefore, more complete approaches were presented. One of them is the (k, l)-anonymity model [18].