Algoritmos e complexidade para anonimização de grau em grafos direcionados
dc.contributor.advisor | Ritt, Marcus Rolf Peter | pt_BR |
dc.contributor.author | Millani, Marcelo Garlet | pt_BR |
dc.date.accessioned | 2015-08-29T02:40:09Z | pt_BR |
dc.date.issued | 2015 | pt_BR |
dc.identifier.uri | http://hdl.handle.net/10183/126063 | pt_BR |
dc.description.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. | en |
dc.description.abstract | 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. | de |
dc.description.abstract | 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. | pt_BR |
dc.format.mimetype | application/pdf | |
dc.language.iso | por | pt_BR |
dc.rights | Open Access | en |
dc.subject | Algoritmos | pt_BR |
dc.subject | Grafos | pt_BR |
dc.title | Algoritmos e complexidade para anonimização de grau em grafos direcionados | pt_BR |
dc.type | Trabalho de conclusão de graduação | pt_BR |
dc.identifier.nrb | 000972315 | pt_BR |
dc.degree.grantor | Universidade Federal do Rio Grande do Sul | pt_BR |
dc.degree.department | Instituto de Informática | pt_BR |
dc.degree.local | Porto Alegre, BR-RS | pt_BR |
dc.degree.date | 2015 | pt_BR |
dc.degree.graduation | Ciência da Computação: Ênfase em Engenharia da Computação: Bacharelado | pt_BR |
dc.degree.level | graduação | pt_BR |
Este item está licenciado na Creative Commons License
-
TCC Ciência da Computação (1000)