@article {das10arxiv_social,
title = {Anonimos: An LP based Approach for Anonymizing Weighted Social Network Graphs},
journal = {IEEE Transactions on Knowledge and Data Engineering},
year = {2010},
pages = {1{\textendash}14},
publisher = {IEEE Computer Society},
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{\'o}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 graph-theoretic algorithms such as
shortest paths problem, k-nearest neighbors, minimum cost spanning
tree, and maximizing information spread. As a proof of concept,
we apply An{\'o}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{\'o}nimos anonymizes the weights, improves
k-anonymity of the weights, and also scrambles the relative
ordering of the edges sorted by weights, thereby providing robust
and effective anonymization of the sensitive edge-weights. Additionally,
we demonstrate the composability of different models generated
using An{\'o}nimos, a property that allows a single anonymized
graph to preserve multiple linear properties.},
keywords = {Anonymization, Linear Programming, Shortest paths, Social Networks, Weighted network models},
author = {Sudipto Das and {\"O}mer E{\u g}ecio{\u g}lu and Amr El Abbadi}
}