  Enormous amounts of data collected from social networks or other online
platforms are being published 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. We propose
and study a new multi-objective anonymization approach that generalizes the
known degree anonymization problem and attempts at improving it as a more
realistic model for data security/privacy. Our suggested model guarantees a
convenient privacy level based on modifying 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.
The corresponding multi-objective graph realization approach is solved using
Integer Linear Programming to obtain the best possible solutions. Our
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 data privacy.
