Algoritmos e complexidade para anonimização de grau em grafos direcionados

Abstract

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.

Die Bedeutung von sozialen Netzwerken für Data Mining ist stark gestiegen, aber deren Anonymisierung ist keine einfache Aufgabe. Diese Arbeit beschäftigt sich mit dem k- Anonymisierungproblem in gerichteten Graphen, wobei ein Digraph k-Anonym ist wenn es für jeder Knoten mindestens k − 1 anderen Knoten mit gleichen Grad gibt. Dieses Modell nimmt an, dass ein Angreifer, der ein Netzwerk deanonymizieren will, den Grad der Knoten im originalen Digraph weiß. Wir untersuchen die Komplexität des Problems, und beweisen NP-schwere und FPT- sowie Polynomialzeit Inapproximierbarkeit. Weiterhin analysieren wir den Spezialfall mit geringem Maximalgrad und stellen effiziente Algorithmen dafür vor.

A relevância de redes sociais para mineração de dados cresceu consideravelmente nos últimos anos. No entanto, já foi mostrado que a preservação da anonimidade dos usuários envolvidos não é uma tarefa fácil. Neste trabalho, consideramos o problema de k-anonimidade em grafos direcionados (dígrafos), onde um dígrafo é considerado k-anônimo quando para cada um de seus vértices existe pelo menos k−1 outros vértices com o mesmo grau. Esse modelo assume que um agressor tentando desanonimizar a rede conhece os graus do vértices do dígrafo original. Nós analisamos a complexidade do problema, provando sua NP-dificuldade e sua inaproximabilidade em tempo polinomial e FPT. Finalmente, investigamos o caso especial onde o grau é limitado e propomos uma solução eficiente para ele.