# FSOpt_k: Finding the Optimal Anonymization Level for a Social Network Graph
## 2 Related Work  
Nowadays, privacy-preserving data publishing is a popular subject. It is employed in both databases and social networks. It benefits from astonishing the adversary in order to avoid him/her discovering the node belonging to a victim in the social network graph. In this section, a brief review of the methods in privacy-preserving graph publishing is represented.  
In general, there are three kinds of threats in a social network graph: identity disclosure, attribute disclosure, and link disclosure. Identity disclosure refers to discovering the user's identity that is related to a node in the social network graph. Attribute disclosure occurs when the sensitive attribute of a node is revealed, and link disclosure is related to the exposure of the sensitive relationship between two users in the social network graph. In this paper, identity anonymization is taken into consideration since it is more general than attribute anonymization. If the user's identity is hidden in the social network graph, their attributes will be hidden too.  
There are lots of works that have been carried out on identity anonymization in social networks. Generally, these works are divided into three categories: graph modification techniques, generalization techniques, and approaches based on privacy-aware computation [6]. Figure 1 demonstrates a categorization of the privacy-preserving graph publishing techniques. The techniques in each category are discussed in the following paragraphs.  
Modification techniques change the graph by adding or deleting some nodes or vertices from the graph. This method adds noise to the nodes or edges of the graph. This technique is employed on weighted and unweighted graphs. In a weighted graph, each edge has a label corresponding to the attributes of the edge. This label can be some criterion to show the strength of the relationship between users. In addition to the edges of the graph, each vertex can have a label too. It can be the users' characteristics, such as his/her age, job, etc. Generalization approaches cluster nodes in the graph to supernodes and edges to super edges. This provides an abstraction of the graph. The anonymous graph has fewer edges and vertices than the original one. Contrary to the increase in anonymity, it decreases the data utility of the graph. Compared with the previous methods, this method has less computational time and can be used on a large network. This method prevents all three types of attacks, i.e., identity disclosure, attribute disclosure, and link disclosure. Finally, privacy-aware computation does not release the graph structure, and the query results are published to the analyzer. One type of privacy-aware computation approach is differential privacy [7]. Differential privacy guarantees that the existence or inexistence of an individual in the dataset does not affect the query results. Therefore, it ensures the user's privacy in the social network graph.  
In this paper, the graph modification technique (as shown in Figure 1) is taken into account, which has been a widely used technique recently. The bold line in this figure demonstrates the scope of the current study. This technique is discussed in the following section.