# A Multi-Objective Degree-Based Network Anonymization Method
## 2 Preliminaries  
We assume familiarity with basic graph theory terminology such as adjacency, vertex degree, and neighborhood, among others. Networks, or graphs, are often subject to attacks that are based upon some prior or presumed knowledge about the degrees of some targeted nodes. This is assumed to be one of the most significant types of attacks [3], since it could threaten individuals' privacy by inferring knowledge about the links to a node and the topology of the graph. Other types of attacks that rely on a priori knowledge of the neighborhood of a targeted node, or the corresponding induced subgraph, can be reduced down to knowledge about the degree of that targeted node. To cope with the above threats, several methods for network data anonymization have been introduced based on the \"hiding in the crowd\" approach. Popular methods include clustering-based anonymization (see [4; 5; 6]) and degree-based anonymization, which we address in this paper. In general, the \(k\)-anonymity model aims at altering the structure of a given graph by adding and/or deleting edges or nodes such that each node in the resulting graph is similar to at least \(k-1\) other nodes, in terms of a specific property [7; 8]. The \(k\)-degree-anonymity approach specifies that nodes are indistinguishable by their degrees. Each graph \(G\) can be represented by a sorted (often decreasing) sequence of the degrees of its vertices. We refer to this sequence by \(D(G)\), being unique for \(G\). The notion of the \(k\)-degree anonymity of a graph can, thus, be reduced to a transformation of its degree sequence into an anonymized one. We seek a minimal number of edge-editing operations. Definition 1: Generally, a degree sequence \(D(G)\) is \(k\)-anonymous if every value in \(D(G)\) is repeated at least \(k-1\) times. Then, a graph \(G\) is \(k\)-degree anonymous if its degree sequence is \(k\)-anonymous. Our approach is divided into two parts. In the first, the descending degree sequence \(D(G)\) is computed and anonymized to produce a degree sequence \(D^{\prime}\). In the second part, \(G^{\prime}\) is constructed so that \(D^{\prime}=D(G^{\prime})\). This latter procedure is known as graph realization, which we formulate as an ILP problem. Previous Edge-Editing Methods  
The first degree-based anonymization approach seems to be due to [PERSON] and [PERSON] [9], who proposed a technique that modifies a given graph/network by adding/deleting a certain number of edges to generate a \(k\)-degree anonymous graph. While the work of [PERSON] and [PERSON] is motivated by logical intuitions, they admit that additional work needs to be carried out to develop theoretically and practically sound privacy models for graphs. In some other attempts, the set of vertices is changed instead of the set of edges. For example, [PERSON] et al. proposed an approach that generates new edges between auxiliary and real nodes or between auxiliary nodes [10]. For unlabeled graphs, experimental results demonstrated that perturbing the set of vertices changes some important properties of a graph (such as how the nodes cluster) and weakens the \"data accuracy\" because of the information loss. In [11], [PERSON] et al. presented an algorithm for graph anonymization based on the univariate micro-aggregation. It works by modifying the set of edges, based on the univariate micro-aggregation method for data protection. Another approach by [PERSON] et al., named the \"GAGA Graph Anonymizer\", was published in 2019 [12]. Their \"Genetic Algorithm for Graph Anonymization\" is claimed to be the best solution for networks' protection because it overcomes all of the limitations of other available solutions. Another genetic algorithm was presented in [13]. Genetic algorithms, however, are known for their limitation in guaranteeing an optimal (or near-optimal) solution. Moreover, with the increase in problem size, especially with real large networks, a genetic algorithm tends to slowly converge to a local minimum.