# A Multi-Objective Degree-Based Network Anonymization Method
## 1 Introduction  
Among the available privacy-preserving techniques for network-based data, degree anonymization proves to be a practical tool in terms of conserving data utility and resisting re-identification attacks. It works by altering the set of edges of a graph so that nodes are indistinguishable in terms of their degrees. Formally, a graph \(G\) is \(k\)-degree anonymous if, for every vertex \(v\), there are at least \(k-1\) other vertices with the same degree as \(v\)[1]. This particular type of \"hiding in the crowd\" guarantees privacy, because an attacker can identify an individual with a probability of at most \(\frac{1}{k}\), where \(k\) is the anonymity/security level desired by the data publisher.  
Unfortunately, the above classical definition of degree anonymity is too restrictive. Requiring at least \(k\) vertices to have the same degree, for each possible vertex degree, could have a very high edge-modification cost in large networks. An alternative multi-objective optimization approach is proposed in this paper. Our model sets restrictions on the number of added and deleted edges per vertex and relaxes the same-degree restriction by setting a range parameter on the resulting degrees, so they would be required to be close enough, while not affecting the privacy level. Thus, it extends the real applicability of this type of network data anonymization. We formally define degree anonymization as a multi-objective optimization (or multi-parameterized) problem, as follows.  
**Multi-Parameterized Degree Anonymization**  
**Given:** An undirected graph \(G=(V,E)\), positive constraint parameters \(a,d\), a range parameter \(t\), and an anonymization parameter \(k\).  
**Question:** Can we obtain an anonymous graph \(G^{\prime}=(V,E^{\prime})\) by adding at most \(a\) and deleting at most \(d\) edges per single vertex, so that, for each vertex \(v\), we have at least \(k-1\) other vertices whose degrees fall into the interval \([degree(v)-t,degree(v)+t]\)?The anonymization parameter \(k\) is assumed to be pre-defined by the user based on the desired anonymization level and the type of the given data.  
The parameters \(a\), \(d\), and \(t\) are computed by the algorithm, as we propose in this paper, to deliver the least cost target solution. It is worth noting that adding local parameters or constraints, typically in graph modification problems, is known to have a notable positive effect on the problem's complexity, while improving the practicality of the model. This was noted in [2] in the context of (multi-parameterized) Cluster Editing, which inspired the above formulation and the work we present in this paper.  
The above-proposed model is a generalization of the \(k\)-degree anonymization problem, which corresponds to the case where \(t=0\) and \(a=d=|V|-1\). We formulate the resulting graph realization problem as an Integer Linear Programming (ILP) problem. We test the utility of our approach by applying clustering on the initial graph and the modified one after performing our anonymization procedure. The comparison is based on measuring the symmetric difference between clusters. In addition, we compare some graph metrics before and after perturbation.