# 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
By adding noise to the rand parameter, the element x\({}_{i}\) increases proportionally to the \(C_{i}\) value, thereby increasing the probability of merging the lower \(C_{i}\) groups with the other groups. The value of norm (noise) is obtained by the following formula. \[\mathrm{Optimal}_{\mathrm{k}}(\mathrm{G})=\mathrm{Argmin}_{\mathrm{k}}( \eta-u), \tag{2}\]0  
Since the NaFa algorithm is a continuous algorithm, these elements are first quantified in the interval [0, 1] and then determined by the formula below the final value of the element x\({}_{i}\) in the position vector. \[x_{i}= \begin{cases}1\ if\ x_{i}\geq 0.5\\ 0\ if\ x_{i}\leq 0.5\end{cases} . \tag{12}\]  
Then, for each position vector, the fitness function is calculated, and the best is used to create a new population. * Fitness function  
The fitness function is used to measure the quality of position vectors in a population. The fitness function considered in this paper is the degree of utility of the graph over the optimal utility specified by the data owner. Additionally, since the goal is to find the optimal value of k, the maximum value for which the desired utility in the graph g is obtained is calculated. For this purpose, the fitness function is defined as follows:  
\[fitness\ function=|\eta-u|+\frac{1}{k}, \tag{13}\]  
where \(u\)(G) is the utility value obtained for graph G by the FSopt_k algorithm, and \(\eta\) is the desired value of graph utility which is computed based on Equation (1). The k value represents the privacy level of the anonymous degree sequence. The utility of graph \(G\) is calculated by the following formula. \[u(G)=1-\left(\frac{IL}{\max(d)-\min(d)}\right)*\left(\frac{1}{n}\right), \tag{14}\]  
where \(IL\) is the information loss value of the graph and is defined as Equation (15). \(\max(d)\) and \(\min(d)\) denote the maximum and minimum in the graph degree sequence. The \(n\) parameter represents the number of graph nodes. \[IL(P)=\sum_{i=1}^{\omega}SE(g_{i}), \tag{15}\]  
where \(\omega\) is the number of groups in partition \(P\), and \(SE\) is the sum of the errors of group \(g_{i}\) in partition \(P\). The sum of the errors is defined as follows. \[SE(g_{i})=\sum_{j=1}^{n}|d_{j}-\widetilde{d}|, \tag{16}\]  
where \(n\) is the number of degrees in the \(g\) group and \(d\) is the mean of the degrees in the \(g\) group. **Definition 5**. : _Consider the position vector \(X\). The value of \(k\) for vector \(X\) is the minimum size of the groups contained therein and is defined as follows._  
\[k=\min\lvert g_{i}\rvert,\ g_{i}\in X\ \&\ 0\leq i\leq\lvert X\rvert, \tag{17}\]  
where \(g_{i}\) represents the \(g^{\prime}\) ith group in position vector \(X\) and \(\ \lvert g_{i}\rvert\) denotes the number of nodes in group \(g_{i}\). Additionally, \(\ \lvert X\rvert\) indicates the number of groups in position vector \(X\). \[\lvert g_{i}\rvert=\{\sum_{i=\alpha}^{\gamma}C_{i}\ \lvert\ x_{\alpha}=1\ \&\&\ \forall\alpha<j<\gamma:x_{j}=0\}, \tag{18}\]  
where \(\alpha\) and \(\gamma\) are the indexes of the first and last element in the position vector \(X\), respectively. \(C_{i}\) denotes the number of degrees inside the \(i\)th element of the cumulative vector. * Creating new population In the NaFa algorithm, some noise is added to each \(\mathrm{x_{i}}\) element in the position vector \(\mathrm{x}\) to create a new population. Therefore, the value of elements in the new position vector may be out of range [0, 1]. In order to address this problem, the new numbers obtained for the position vector elements are normalized by the following formula to fit into the interval [0, 1]. \[norm(x_{i})=\frac{x_{i-min}}{max-min},\] (19) where \(max\) is the largest number and \(min\) is the lowest number in the position vector. The word norm represents the normal value of \(x_{i}\). Compute the Best Value of k Based on the NaFa Solution  
After the best position vector is obtained by the NaFa algorithm, the optimal value of k is calculated and given as an input to the degree sequence anonymization step.