# FSOpt_k: Finding the Optimal Anonymization Level for a Social Network Graph
## 2 Related Work
#### Graph Modification Techniques
A graph is (k, l)-anonymous if, for each vertex V in the graph, there are at least k-1 other vertices with at least one common neighbor with that vertex. [PERSON] et al. [19] discussed some problems of this work. They argued that [PERSON]'s algorithm causes risk for users when k \(\leq\) l and users can be identified according to their two neighbors. They also propounded a different definition for k-anonymity. According to their definition, a graph is k-anonymous if, for every vertex v1 in the graph, there are at least k other vertices {vi}ki = 1, so that \(\Gamma\)(vi) = \(\Gamma\)(v1) for all i \(\in\) [l, k]. They relaxed the definition of (k, l)-anonymity so that a graph is (k, l)-anonymous if for each vertex v \(\in\) V, there is a subset of u \(\in\) V so that \(\,\mathrm{l}\,\mathrm{U}\,\mathrm{l}\,\mathrm{\geq k}\) and for each u \(\in\) U the two vertices u and v have at least one common neighbor. One problem in the anonymization of social network graphs is the anonymization of hub-like users in the network. The amount of perturbation that needs to be applied to the graph to anonymize these users is high. Therefore, information utility decreases a lot. To overcome this problem, some researchers presented k-subset anonymity that anonymizes just a special subset of vertices so that the number of edges added to the graph is minimized. k-degree-subset-anonymity [20] is a version of this model that anonymizes a subset X \(\subseteq\) V. In this work, the number of edges that are added to the graph should be minimized. Another category of social network graphs is labeled graphs. [PERSON] et al. [21] provided a linear model for k-anonymity aimed at maintaining unchanged graph properties as much as possible. In this work, graph properties consist of the shortest path, k-nearest neighbor, and minimum spanning tree. The graph is assumed to be weighted. [PERSON] et al. [22] focused on the anonymization of the labels in the graph. Its goal is to obtain a graph with an anonymous k-label sequence. The label of each node consists of the tag of the edges incident to it. Additionally, they proved that the problem of k-label sequence anonymity is P for k = 2, but it is NP-hard for k \(>\)= 3. [PERSON] and [PERSON] [23] adapted the notion of k-anonymity and l-diversity to employ a vertex-labeled social network graph. Additionally, they proved that achieving optimal k-anonymity and l-diversity is NP-hard. The same problem was investigated for labels of the edges in the graph [24]. There are some papers that worked on anonymizing the vertex-labeled graph. In this graph, each vertex has an assigned label which contains some information about that vertex. L-diversity cannot preserve the user's privacy when the data is skewed [25]. Therefore, t-closeness was proposed to overcome this problem. In t-closeness, it is guaranteed that the distribution of the data values within each group of data is close to the distribution of data in the entire dataset. Contrary to the fact that t-closeness is strong, it cannot be applied explicitly to the graph [26]. Therefore, a method called \(\alpha\)-proximity was proposed that preserves the user's attributes by adding fake edges to the social network graph [26]. Another algorithm was presented by [PERSON] et al. [27] for k-anonymity and l-diversity on the vertex-labeled graphs. The aim of this method is to change the average path length of the graph as minimally as possible. This algorithm uses fake vertices and edges to anonymize the graph. Some recent methods benefit from the notion of uncertain graphs. Uncertain graphs differ from other kinds of graphs from the perspective that they have edges with weights in the range of 0 to 1. Each weight in these graphs is given by a function to an edge. In this approach, edge weight is increased or decreased in order to anonymize the network. The first method was presented in 2012 by ref. [28]. In this method, removing an edge was carried out by decreasing the edge weight from 1 to 0, and for adding an edge, the edge weight was increased from 0 to 1.