Return to search

Graph anonymization through edge and vertex addition

With an abundance of social network data being released, the need to protect sensitive information within these networks has become an important concern of data publishers. In this thesis we focus on the popular notion of k-anonymization as applied to social network graphs. Given such a network N, the problem we study is to transform N to N', such that some property P of each node in N' is attained by at least k-1 other nodes in N'. We study edge-labeled, vertex-labeled and unlabeled graphs, since instances of each occur in real-world social networks.

Our main contributions are as follows

1. When looking at edge additions, we show that k-label sequence anonymity of arbitrary edge-labeled graphs is NP-complete, and use this fact to prove hardness results for many other recently introduced notions of anonymity. We also present interesting hardness results and algorithms for labeled and unlabeled bipartite graphs.

2. When looking at node additions, we show that on vertex-labeled graphs, the problem is NP-complete. For unlabeled graphs, we give an efficient (near-linear) algorithm and show that it gives solutions that are optimal modulo k, a guarantee that is novel in the literature.


We examine anonymization both from its theoretical foundations and empirically, showing that our proposed algorithms for anonymization maintain structural properties shown to be necessary for graph analysis. / Graduate

Identiferoai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/3755
Date20 December 2011
CreatorsSrivastava, Gautam
ContributorsSrinivasan, Venkatesh, Kapron, Bruce
Source SetsUniversity of Victoria
LanguageEnglish, English
Detected LanguageEnglish
TypeThesis
RightsAvailable to the World Wide Web

Page generated in 0.002 seconds