Abstract  The increasing popularity of social networks has initiated a fertile
research area in information extraction and data mining. Anonymization
of these social graphs is important to facilitate publishing these
data sets for analysis by external entities. Prior work has concentrated
mostly on node identity anonymization and structural
anonymization. But with the growing interest in analyzing social
networks as a weighted network, edge weight anonymization
is also gaining importance. We present Anónimos, a Linear Programming
based technique for anonymization of edge weights that
preserves linear properties of graphs. Such properties form the
foundation of many important graphtheoretic algorithms such as
shortest paths problem, knearest neighbors, minimum cost spanning
tree, and maximizing information spread. As a proof of concept,
we apply Anónimos to the shortest paths problem and its extensions,
prove the correctness, analyze complexity, and experimentally
evaluate it using real social network data sets. Our experiments
demonstrate that Anónimos anonymizes the weights, improves
kanonymity of the weights, and also scrambles the relative
ordering of the edges sorted by weights, thereby providing robust
and effective anonymization of the sensitive edgeweights. Additionally,
we demonstrate the composability of different models generated
using Anónimos, a property that allows a single anonymized
graph to preserve multiple linear properties.
