Degree-Based Network Anonymization

Abstract

Enormous amounts of data collected from social networks or other online platforms are being published publicly for the sake of statistics, marketing, and research, among other objectives. The consequent privacy and data security concerns have motivated the work on degree-based data anonymization. In this thesis, we study a new multi- objective parameterized anonymization approach that generalizes the known degree anonymization problem and attempts at improving it as a more realistic model for data security/privacy. Our model suggests a convenient privacy level for each net- work based on the standard deviation of its degrees. The objective is to modify the degrees in a way that respects some given local restrictions, per node, such that the total modifications at the global level (in the whole graph/network) are bounded by some given value. A corresponding graph realization approach is introduced based on a reduction to the Weighted Edge Cover problem, which in turn is solved using Integer Linear Programming to obtain the best possible solution. Our thorough experimental studies provide empirical evidence of the effectiveness of the new approach; by specifically showing that the introduced anonymization algorithm has a negligible effect on the way nodes are clustered, thereby preserving valuable network information while significantly improving the data privacy.