Anonymizing Edge-Weighted Social Network Graphs


Sudipto Das, Ömer Egecioglu, Amr El Abbadi
Department of Computer Science,
University of California, Santa Barbara
Santa Barbara, CA 93106 - 5110, USA
{sudipto, omer, amr}@cs.ucsb.edu

Abstract

The increasing popularity of social networks has initiated a fertile research area in information extraction and data mining. Although such analysis can facilitate better understanding of sociological, behavioral, and other interesting phenomena, there is growing concern about personal privacy being breached, thereby requiring effective anonymization techniques. If we consider the social graph to be a weighted graph, then the problem of anonymization can be of various types: node identity anonymization, structural anonymization, or edge weight anonymization. In this paper, we consider edge weight anonymization in which the anonymization preserves important properties of the underlying graphs. Our approach builds a linear programming (LP) model which preserves properties of the graph that are expressible as linear functions of the edge weights. Such properties form the foundations of many prevalent graph-theoretic algorithms such as single source shortest paths tree, all-pairs shortest paths, k-nearest neighbors, minimum cost spanning tree, etc. Off-the-shelf LP solvers can be used to find solutions to the resulting model where the computed solutions form the weights of the anonymized graph. We demonstrate how this abstract model can be used for different applications, prove the correctness of the extended models, analyze their complexity for selected graph algorithms, and experimentally evaluate the proposed techniques using real social network data sets.

Categories and Subject Descriptors
E.1 [Data Structures]: Graphs and networks; G.1.6 [Optimization]: Linear programming; J.4 [Social and Behavioral Sciences]: Sociology

General Terms
Algorithms, Design.

Keywords
Anonymization, Social Networks, Shortest paths, Linear Programming.

UCSB Computer Science Technical Report (CS-2009-03), March 2009

Report:2009-03, Official copy