# A Multi-Objective Degree-Based Network Anonymization Method
## 5 Experimental Analysis  
We implemented our multi-objective degree anonymization algorithm and ran multiple tests using different graphs to assess its efficiency and, most importantly, its ability in preserving data utility. It was implemented in \(Java\), and we used \(CPLEX\) for the realization algorithm. The tests were performed on an Intel(R) Core(TM) i7-7600U CPU @ 2.80 GHz machine. Various values of \(k\) were tested while \(t\) was set to 2.  
We compared our results with the ones presented in [16] for the algorithm of [PERSON] (\(k\)-Degree Anonymization: \(k\)-\(DA\)). We also compared our algorithm to the vertex addition approach by [PERSON] et al. [10], in which the anonymization process takes place by adding fake vertices to the network and fake edges between these vertices, and between fake vertices and real ones, to attain the required \(k\)-anonymity level. Finally, we comparedour results with [PERSON] et al.'s results in [11]. Their algorithm is based on the univariate micro-aggregation. It is available in two versions. The first, dubbed \"NC\", is based on the notion of neighborhood centrality, to decide which edges to delete. It tries to preserve the edges that are more relevant to the connectivity of the whole network than others. The second approach (\"Rand\") randomly selects edges to be removed. We used the authors' published results for comparison.  
Real data sets were used for testing. The selected networks were obtained from the KONECT Project [17]. They are different in terms of topological, structural, and attribute properties. However, all of the graphs used are simple, unweighted, and undirected. The following were chosen:  
* US politics book data (Polbooks-2004) [18] is a network of US politics' books where vertices represent books and an edge between two vertices implies that they are co-purchased frequently by the same buyers.
* Polblogs [19], which stands for political blog-sphere data, is a network that compiles data about links between US political blogs.
* GrQc [20] is a collaboration network that displays collaborations between authors and scientific papers in the field of General Relativity and Quantum Cosmology.
* American college football [21] is a network of American football games during Fall 2000. A vertex represents a playing team, and an edge between two teams means that they have played together.
* Erdos [17] network is a graph that shows a list of mathematician [PERSON] co-authors along with their respective co-authors.
* The Enron [22] email network covers all email communications within a dataset of around half a million emails.  
The notion of data utility is not well-defined yet, so different authors have different approaches in quantifying data loss in a graph. In our work, we use the following graph structural measures to quantify and analyze information loss induced by the anonymization process:  
* The largest eigenvalue of the adjacency matrix implies information about the diameter of a network and its cycles.
* The second smallest eigenvalue of the Laplacian matrix implies information about the tree structure of the graph. It shows if the communities separate efficiently or not.
* The average distance is the average of the shortest paths between all nodes in a network.
* The harmonic mean of the shortest distance is similar to the average distance; it is used to evaluate the connectivity of a network.
* Modularity measures the strength of the division of a network into clusters. High modularity values imply dense connections between the nodes of a graph.
* Transitivity is similar to the clustering coefficient; it detects the presence of loops near a vertex.
* Subgraph centrality measures the number of subgraphs a vertex takes part in, weighting them according to their size.