# FSOpt_k: Finding the Optimal Anonymization Level for a Social Network Graph
## 2 Related Work
#### Graph Modification Techniques
Edge weights are within the range [0, 1]. Therefore, edge weights can be considered edge probabilities. Additionally, they introduced the notion of a (k, \(\varepsilon\))-obfuscation graph. A graph is k-obfuscation with respect to a property P if the entropy of the distribution Yp(v) over the vertices of the graph is greater than or equal to log2k. A graph is (k, \(\varepsilon\))-obfuscation with respect to P if at least (1 - \(\varepsilon\))*n vertices are k-obfuscated. Another method was presented in 2015 by ref. [29]. This method is a generalized view of graph modification based on the notion of the uncertain adjacency matrix of the graph. Another method was provided by the same authors that used maximum variance to obtain a better tradeoff between privacy and data utility [30]. Some works were conducted on accessing private data in social networks. [PERSON] et al. [31] proposed a method that assesses private data access for social network security. In this work, the normal private data access pattern is determined in advance. Therefore, any abnormal data access pattern can be identified. It uses Bayesian probability to make normal patterns for private data accesses. [PERSON] et al. [32] also proposed a graph modification technique that changes the edges of the graph by preserving the core of the graph so that the structure of the graph community is preserved. Although this algorithm preserves the core number of vertices after anonymity, by changing the level of the anonymization of the graph, the algorithm must be run from the beginning, which is time-consuming. [PERSON] et al. [33] provided an overview of privacy techniques and divided existing techniques into two categories: node privacy techniques and edge privacy techniques. [PERSON] et al. [34] proposed a user privacy exposure measure to evaluate the privacy of users who contribute to multiple online social networks. In addition, they considered the information loss reduction. [PERSON] et al. [35] proposed an algorithm for anonymizing a dynamic directional graph degree sequence that uses the addition of artificial nodes to the graph and, as the node is added, groups it. Then, the nodes that make the least change to the graph structure are connected. In the same year, [PERSON] et al. [36] considered user-level privacy at the network level rather than the user-level and developed a method that clustered nodes, edges, and attributes by clustering users based on feature similarity. In this method, in addition to the k-anonymity model, the l-diversity model is also considered. Additionally, [PERSON] et al. [37] presented a time and memory-saving algorithm which uses a tree structure to anonymize the degree sequence of the graph. [PERSON] et al. [38] proved in 2021 that the minimum number of edge rotations to anonymize a social network graph is NP-hard. In the same year, [PERSON] [39] proposed an algorithm that anonymizes the social network graph with the least number of edges added to the graph. [PERSON] et al. [40] examined the mutual friendsattack model and developed an algorithm that also supports k-degree attacks. Finally, in the same year, [PERSON] et al. [41] developed a fast method for modifying social network graphs that ensures the k-degree anonymity model. In this method, an effective method was used to identify and select the appropriate edges for graph editing, which increases the utility of the graph while reducing execution time. [PERSON] et al. [42] presented an algorithm for the social network graph k-anonymization problem, which used the tree structure to anonymize the degree sequence of the graph and improve the usefulness of the anonymous graph. In the same year, [PERSON] et al. [43] presented a new technique that reduces the amount of noise applied to the data and reduces the d-neighborhood attack of the graph. In this technique, edges and vertices were anonymized. Table 1 underlines some recent methods in graph modification techniques.