Open Collections

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

University of British Columbia

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.

Text

2018-01-08

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/64311

Computer Science

University of British Columbia

UBCO

http://creativecommons.org/licenses/by-nc-nd/4.0/