Back to search

University of Victoria (Canada)

Graph anonymization through edge and vertex addition

Abstract

dc:description.abstract

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.

Degree

thesis:*
Level thesis:degree_level
Doctor of Philosophy Ph.D.
Department thesis:degree_department
Department of Computer Science
Year dc:date.issued
2011

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Srivastava, Gautam
Advisors dc:contributor.supervisor
  • Srinivasan, Venkatesh
  • Kapron, Bruce

Subjects

dc:subject × 8

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web
Language dc:language.iso
en, English

Identifiers

dc:identifier.*
Dc Identifier Citation
Sean Chester, Bruce Kapron, Ganesh Ramesh, Gautam Srivastava, and S. Venkatesh. k-anonymization of social networks by vertex addition. In Advances in Databases and Information Systems, ADBIS, 2011.
Sean Chester and Gautam Srivastava. Social network privacy for attribute disclosure attacks. In Advances in Social Networks Analysis and Mining, ASONAM, 2011.
Bruce Kapron, Gautam Srivastava, and S. Venkatesh. Social network anonymization via edge addition. In Advances in Social Networks Analysis and Mining, ASONAM, 2011.

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Srivastava, Gautam. Graph anonymization through edge and vertex addition. Doctor of Philosophy Ph.D. thesis, 2011. http://hdl.handle.net/1828/3755