# 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
The goal is to find the best partition in this aggregate vector so that we have the least amount of information loss for the highest k value obtained by the algorithm. Since finding the best partitioning in the aggregate vector AV is an NP problem, this paper uses the NaFa algorithm [5] to find it. The steps of this algorithm will be explained in the following sections. Employing NaFa to Find the Best Solution  
After creating the aggregate vector, it can be used to determine the optimal value of k. In order to find the best value of k, all of the cases should be investigated. Therefore, it is an NP problem. Hence, an optimization algorithm is needed to handle this issue. For this purpose, in this paper, the NaFa optimization algorithm [5] is used. This algorithm is an improved version of the firefly algorithm. In NaFA, each firefly is drawn from a predefined neighborhood rather than the entire population to the other brighter fireflies. The rate of firefly i motion in this algorithm is determined by Equation (5). \[x_{id}(t+1)=x_{id}(t)+\beta\Big{(}x_{jd}(t)-x_{id}(t)\Big{)}+\alpha(t)s_{d}c \dot{i}, \tag{5}\]  
where \(c\dot{i}\) is a random number from the interval [\(-0.5\), \(0.5\)], \(\alpha\) is the step factor from the interval [\(0\), \(1\)], and \(s_{d}\) is the length scale of each variable described. The \(\beta\) value represents the absorption rate, determined by Equation (6), between two fireflies. \[\beta=\ \beta_{min}\ +(\ \beta_{0}\ -\beta_{min}\ )\mathrm{e}^{-\gamma r_{i}^{2}}. \tag{6}\]  
In this formula, \(\beta\)min is the minimum value of \(\beta\), \(\gamma\) is the light absorption coefficient, and \(r\dot{i}\) is the distance between the two fireflies i and j. The value of \(\alpha\) is obtained by Equation (7). \[\alpha(t+1)=\bigg{(}\frac{1}{9000}\bigg{)}^{\frac{1}{t}}\alpha(t). \tag{7}\]  
In order to use NaFa, position vectors should be initialized. Position vectors in the NaFa algorithm are formed based on the aggregate vector described before. In fact, each element in the position vector contains one element in the aggregate vector. Then, the NaFa algorithm finds the best partition in this vector. The details of each of these steps are described below. * Initial population creation  
The initial population in the NaFa algorithm is the number of \(x_{i}\) position vectors. Suppose \(Lx\) is the length vector of the position \(x_{i}\) in this population. The \(Lx\) value is equal to \(|\)AV (G)\(|\), where AV (G) is the aggregate vector of the graph G and \(|\)AV (G)\(|\) shows the length of this vector. For each element in the position vector \(x\), the following relation exists. \[\forall x_{i}\in x,\ x_{0}=1\ \&\ x_{j}\in\{0,\ 1\}\ \big{|}\ 1\leq j\leq i. \tag{8}\]Each element in the position vector x corresponds to one element in the aggregate vector AV, and the value 1 for x\({}_{i}\) represents a new group in the partition. The first element in the aggregate vector always starts the first group in the partition, x\({}_{0}\) = 1. Therefore, any group g\({}_{k}\) in the \(P\) partition can be defined as follows. \[g_{k}(P)=\{U_{i=s_{i}}^{s_{i+1-1}}(C_{i},\ D_{i})\in AV(G)\ |\ x_{si}=1\ \&\&\forall s_{i}<j<s_{i+1},\ x_{j}=0\}, \tag{9}\]  
where \(si\) is an element index in the position vector x whose value is 1. The elements in the position vector x in the interval (s\({}_{i},s_{i+1}\)) have a value of 0. In this paper, the following formula is used to initialize position vector elements. \[x_{i}=rand+norm(noise), \tag{10}\]  
where rand is a random number within the range [0, 1]. The numerical noise value is proportional to the value of \(C_{i}\) in the \(i\)th element of the experimental vector. As mentioned earlier, \(C_{i}\) is the number of degrees i in the graph degree sequence. The reason for using the noise parameter is that the elements of the cumulative vector that have less \(C_{i}\) must be merged with more elements of the cumulative vector to create an anonymous graph.