Repositório Digital

A- A A+

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

.

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

Mostrar registro completo

Estatísticas

Título Algoritmos e complexidade para anonimização de grau em grafos direcionados
Autor Millani, Marcelo Garlet
Orientador Ritt, Marcus Rolf Peter
Data 2015
Nível Graduação
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Curso de Ciência da Computação: Ênfase em Engenharia da Computação: Bacharelado.
Assunto Algoritmos
Grafos
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.
Zusammenfassung 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.
Resumo 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.
Tipo Trabalho de conclusão de graduação
URI http://hdl.handle.net/10183/126063
Arquivos Descrição Formato
000972315.pdf (640.0Kb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.