Obtaining k-degree anonymous networks via mathematical programming

Social network data sets are often published and used for analysis purposes in many application domains. This frequently raises privacy issues, as simply hiding users’ identities does not prevent potential adversaries from tracing back to the real-world entities associated with specific nodes of the network having sufficiently distinctive features from others. To protect individuals’ privacy, networks need to be properly anonymized before publication. The k-degree anonymization problem is to determine the smallest set of edge modifications needed to ensure that each user has the same number of connections as at least k−1 other users. A network satisfying this property is defined as k-degree anonymous. In this work, we tackle three versions of the problem allowing for edge insertions and deletions, exclusively or together. This work is the first to apply integer linear programming (ILP) techniques to k-degree anonymous networks. We introduce two families of ILP formulations and propose an ILP-based heuristic approach based on imposing that the order of the nodes inherited from its degree sequence remains unchanged after performing the modifications, which allows for an efficient ILP reformulation with the k-degree anonymity constraints. We additionally derive combinatorial bounds on the largest degree of the anonymized network, helping reduce the size of the proposed formulations. Finally, we conduct computational experiments on benchmark social networks and scale-free networks, we compare the obtained results with those produced by two state-of-the-art approaches, and we perform an instance space analysis to identify the features that mostly affect the performance of the formulations.