# FSOpt_k: Finding the Optimal Anonymization Level for a Social Network Graph
## 6 Experimental Results
### Information Loss Metrics
#### 6.2.2 General Properties of Graph Analysis  
In order to evaluate the proposed algorithm in terms of general graph properties, four metrics are evaluated, including average path length, transitivity, average clustering coefficient, and modularity. The more the similarity between the values of these parameters is in the main graph and the anonymous graph, the more the graph's utility can be preserved by the algorithm. These parameters are explained below. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Data Sets** & \multicolumn{2}{c}{**Characteristics**} \\ \hline  & **Nodes** & **Edges** \\ \hline Dolphins & 62 & 159 \\ Netscience & 1589 & 2742 \\ Polbooks & 105 & 441 \\ Power Grid & 4941 & 6594 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Attributes of the benchmark datasets. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Data Sets** & \multicolumn{5}{c}{**FSopt\_k**} & \multicolumn{2}{c}{**UMGA**} \\ \hline  & \(\mathcal{L}\) & **Desired Utility** & **Obtained k Value** & **Obtained Utility** & _k Value_ & **Utility** \\ \hline  & 0.05 & 0.974633443 & 10 & 0.94134 & 8 & 0.973607 \\ Dolphins & 0.1 & 0.94369499 & 14 & 0.935483 & 13 & 0.938416 \\  & 0.2 & 0.91612901 & 20 & 0.9149560 & 20 & 0.914956 \\ \hline  & 0.05 & 0.997917 & 10 & 0.9971 & 13 & 0.9979023 \\ netscience & 0.1  
* Average path length (APL) measures the average length of the shortest paths in the social network graph between vertices. This parameter is one of the most important graph analysis criteria and is defined as Equation (25). \[APL(G)=\frac{1}{n(n-1)}*\sum_{i\
eq j}d(v_{i},v_{j}),\] (25) where d (v\({}_{i}\), v\({}_{j}\)) denotes the shortest path length between each of the v\({}_{i}\) and v\({}_{j}\) nodes, and n indicates the number of graph nodes. * Transitivity (T) is a further criterion utilized to assess FSopt_k, which measures the relative number of triangles in a graph and is defined as Equation (26). \[Transitivity=\frac{3*\Delta}{\wedge},\] (26) where \(\Delta\) refers to the number of triangles, and \(\wedge\) denotes the number of paths with length two. * Average clustering coefficient (ACC) measures the closeness of the neighbors of each of the graph nodes to the full graph. This criterion is defined in Equation (27). \[ACC(G)=\frac{1}{n}*\sum_{u=1}^{u}\frac{2T(u)}{\text{deg}(u)*(\text{deg}(u)-1)},\] (27) where \(u\) shows a node in the graph, n denotes the number of graph nodes, and \(\text{deg}(u)\) represents the degree of node \(u\). * Modularity (mod) is one of the criteria used to measure the strength of the network division into modules. The results of FSopt_k evaluation from the aspect of general graph properties on the datasets are shown in Figures 8-11. The vertical axis in these figures represents the error value related to the graph's general properties, and the horizontal axis shows the evaluation metrics. The error value is measured by (32) [37] for each metric. The lower the error value is, the better the algorithm performs. \[\text{Error}=|\text{ATTRIB}_{i}-\text{ATTRIB}|, \tag{28}\]  
where ATTRIB\({}_{i}\) is the value of evaluation criteria evaluated for the optimal k value obtained by FSopt_k. The ATTRIB parameter shows the evaluation criteria. The evaluation results of the algorithms presented in this paper on the Dolphins dataset for different values of L are shown in Figure 8. As the figure shows, the FSopt_k algorithm works better than UMGA in all cases. The reason for this improvement is the use of the coreness and PL criteria when selecting the best edge to remove or add. By increasing the value of \(\mathcal{L}\), we have almost similar results on this dataset. For the value of \(\mathcal{L}=0.1\), the proposed algorithm performs better than other algorithms in most cases. The only criterion in which the accuracy of the algorithm is reduced is the T criterion. In this case, the accuracy of the algorithm is not reduced too significantly.