Algorithms and Complexity for Degree Anonymization in Directed Graphs

Marcelo Garlet Millani (UFRGS, Porto Alegre, Brasilien)

Social networks had an ever increasing relevance for data mining, yet preserving the anonymity of users was already shown to be no simple task. In this work we consider the k-anonymity problem in directed graphs, where a digraph is k-anonymous if for every vertex there are at least k −1 other vertices with the same degree. The assumption of this model is that an attacker attempting to deanonymize the network knows the degrees of the vertices in the original digraph. We analyze the complexity of the problem, proving NP-hardness, polynomial-time inapproximability and FPT-time inapproximability. Finally, we investigate the special case where the degree is bounded and provide an efficient solution for maximum degree one.

Back to the research colloquium site.