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