Back to search

University of British Columbia

A study on a privacy measure for social networks : computational complexity and properties on random graphs

Abstract

dc:description

As the booming of social networks, network analysis has benefited greatly from released network data. Meanwhile, the leakage of users' information is becoming more and more serious. The users' personal information may be compromised even if the data are anonymized before being released. Adversaries can uniquely re-identify a user in an anonymized social network by the quasi-identifiers as their background knowledge. To measure the resistance against privacy attacks in anonymized social networks where the background knowledge of adversaries is the metric representation, R. Trujillo-Rasua and I.G. Yero introduced a new measure: (k,l)-anonymity based on the notions k-antiresolving set and k-metric antidimension in 2016. In this thesis, we prove that the problem of computing k-metric antidimension is NP-hard by a polynomial-time reduction from a well-known NP-complete problem, the exact cover by the 3-sets problem (X3C problem), to a decision version of the problem of computing k-metric antidimension. With this conclusion, we prove that the (k,l)-anonymity problem is NP-complete. Also, in the hope to get a general relation between k and l in the (k,l)-anonymity problem, we study the behaviors of k-antiresolving sets in Erdos-Renyi random graphs. We establish three bounds on the size of k-antiresolving sets in Erdos-Renyi random graphs leading to a range of k-metric antidimension where k is constant.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhang, Congsong

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/64311

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Zhang, Congsong. A study on a privacy measure for social networks : computational complexity and properties on random graphs. master's thesis, University of British Columbia, 2017. http://hdl.handle.net/2429/64311