# FSOpt_k: Finding the Optimal Anonymization Level for a Social Network Graph
## 4 FSOpt_k Algorithm
### Details of the Proposed Algorithm
#### 4.2.1 Finding the Optimal Value of k for the Graph  
As discussed earlier, choosing the correct value for the k parameter as the privacy level has a great impact on the utility of the anonymous graph. For this reason, an algorithm will be presented in this section that can find the optimal value of k with respect to the degree sequence of the social network. In this paper, we define the optimal value of k as defined by Equation (1). **Definition 4**. : _Consider the social network graph G. The maximum value of k, which, if applied to graph G, results in the creation of an anonymous graph with desired \(\eta\), is called the optimal value of k. Desired utility \(\eta\) is calculated by the user-specified coefficient. This factor determines the user's opinion of the percentage of the graph's utility changes. The utility of the graph can be varied for different values of k. This value is calculated by the following formula._  
\[\eta=max(u)-\mathcal{L}\times(\ max(u)-min(u)\ ), \tag{1}\]  
where max (\(u\)) and min (\(u\)) are the maximum and minimum utility of the graph, respectively, and \(\mathcal{L}\) is the coefficient of variation of the utility that is determined by the user. The maximum utility is when k = 2, and the minimum utility occurs with the privacy level k = n, where n is the number of graph nodes. The u parameter indicates the utility of the graph. The Formula (14) describes how to obtain it. Then, the optimal value of k can be expressed by the following equation. \[\mathrm{Optimal}_{\mathrm{k}}(\mathrm{G})=\mathrm{Argmin}_{\mathrm{k}}( \eta-u), \tag{2}\]  
where n represents the value of the optimal utility from the user's perspective and \(u\) denotes the utility of graph G.  
To find the best value of k, first, an aggregate vector of the graph degree sequence is created. In this vector, which is a compact version of the graph degree sequence, each node contains several nodes of the graph degree sequence. This vector is given as input to the NaFa algorithm, and then, the best partitioning for the graph is determined by the NaFa algorithm. Finally, the optimal value of k is determined by this partitioning. Algorithm 1 shows the way of finding the optimal value of k for graph G. Each of the steps of this algorithm will be explained in the following sections. The number written against each step of this algorithm represents the part of the article that describes the details of that step. ```
Input: graph G Output: the best value of k  Create the aggregate vector of G  Employ NaFa to find the best solution  Compute the best value of k based on the NaFa solution  Return k value
```  
**Algorithm 1** Finding the optimal value of k  
Creating an Aggregate Vector  
The first line of Algorithm 1 creates a compact vector of the graph degree sequence. This compact vector results in faster operation and, thus, lowers the execution time of the algorithm. To this end, we use the method presented in ref. [37]. Each node in this compact vector contains a number of nodes in the same social network graph. If the degree sequence d = {d1, d2,..., dn} is given by the graph, where di is the degree of node vi, to create an aggregate vector, the degree sequence is first ascended so that d1 \(\leq\) d2 \(\leq\) d3 \(\leq\)... \(\leq\) dn. Then, the aggregate vector consists of finding the vertices (\(n_{i}\), \(n_{j}\)) such that \(d_{i}=d_{j}\). In this paper, we show the number of vertices with equal degrees in the arranged degree sequence \(d\) by \(c\) which is defined as follows. \[c_{i}=\{\ |U_{i=1}^{\text{num}}n_{i}|\ \mid\ d_{i}=d_{i+1}\ \}, \tag{3}\]  
where num is the number of consecutive nodes of the same order in the ordered degree sequence of the graph. Each of the degrees, together with the number of nodes of that degree, forms one element of the aggregate vector. The aggregate vector is defined as follows [37]. \[\text{AV}(G)=U_{i=1}^{|c|}c_{i}, \tag{4}\]  
where \(|c|\) is the size of the c collection which was constructed by Equation (3).