Anonymizing Edge-Weighted Social Network Graphs

Date Added: Jun 2009
Format: PDF

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 the authors 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, they consider edge weight anonymization. Their approach builds a Linear Programming (LP) model which preserves properties of the graph that are expressible as linear functions of the edge weights.