Anonimos: An LP based Approach for Anonymizing Weighted Social Network Graphs

TitleAnonimos: An LP based Approach for Anonymizing Weighted Social Network Graphs
Publication TypeJournal Article
Year of Publication2010
AuthorsDas, S, Eğecioğlu Ö, El Abbadi A
JournalIEEE Transactions on Knowledge and Data Engineering
PublisherIEEE Computer Society
KeywordsAnonymization, Linear Programming, Shortest paths, Social Networks, Weighted network models

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 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ó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
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ónimos, a property that allows a single anonymized
graph to preserve multiple linear properties.

Refereed DesignationRefereed