Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/36705
Type: | Dissertação |
Title: | Algoritmos para o problema de nilcatenation com aplicação na detecção de lavagem de dinheiro em criptomoedas |
Authors: | Clynton Augusto Tomacheski Amaral |
First Advisor: | Sebastián Alberto Urrutia |
First Co-advisor: | Anolan Yamilé Milanés Barrientos |
First Referee: | Thiago Ferreira de Noronha |
Second Referee: | Jeroen Antonius Maria van de Graaf |
Third Referee: | João Fernando Machry Sarubbi |
Abstract: | O saldo de um vértice é definido como a diferença entre a soma dos pesos dos arcos que entram e os arcos que saem do vértice. Desse modo, o Problema de Nilcatenation (NCP) consiste em encontrar um subconjunto de arcos que pode ser removido de forma segura sem alterar o saldo de nenhum vértice. Neste trabalho, o NCP é analisado teoricamente, sendo apresentada uma nova prova de NP-completude e uma primeira formulação de programação linear inteira. Além disso, são introduzidos um conjunto de grafos de teste e mecanismos para o préprocessamento de instâncias do problema. Ademais, é apresentada uma comparação experimental do método de branch and bound e do algoritmo de local branching, ambos utilizando a formulação proposta. Os resultados experimentais mostram que o algoritmo de local branching tem desempenho melhor ou igual na maioria das instâncias de teste. Seguindo a premissa que o histórico de transações de uma criptomoeda pode ser modelado como um grafo, este trabalho também propõe a aplicação do NCP como um mecanismo para identificar padrões de lavagem de dinheiro em um grafo gerado a partir das transações de uma criptomoeda. Considerando a crescente importância das criptomoedas no mundo financeiro e que uma de suas principais criticas é sua exploração em atividades ilícitas, este trabalho apresenta um estudo experimental dos algoritmos propostos aplicados à transações extraídas do histórico de transações do Bitcoin, demonstrando a viabilidade da aplicação do NCP neste contexto. |
Abstract: | The balance of a vertex is the difference between the sum of weights of arcs entering and arcs leaving the vertex. Thus, the Nilcatenation Problem (NCP) consists of finding a subset of arcs that can be safely removed without modifying the balance of any vertex. This work analyses theoretically the NCP, presenting a new NP-completeness proof, and a first linear integer programming formulation. Moreover, it introduces a set of benchmark instances and mechanisms for NCP instances preprocessing. Furthermore, the study presents an experimental comparison of the branch and bound methoda nd the local branching algorithm, both of them using the proposed formulation. Experimental results show that the local branching algorithm performs equally or better on the majority of the instances. Following the premise that it is possible to model a cryptocurrency transaction history as a graph, this work also expands the NCP usage as a method to detect possible money laundering patterns on graphs generated by cryptocurrency transactions. Considering the cryptocurrencies growing importance in the financial world and one of its main critiques is that cryptocurrencies can be exploited as a tool for criminal activity, this work presents an experimental study of the proposed algorithms applied to transactions extracted from Bitcoin’s blockchain, demonstrating the viability of the NCP employment in such context. |
Subject: | Computação – Teses Algoritmos em Grafos – Teses Programação Inteira – Tese Lavagem de Dinheiro – Teses Bitcoin – Teses |
language: | por |
metadata.dc.publisher.country: | Brasil |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
metadata.dc.publisher.department: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
metadata.dc.publisher.program: | Programa de Pós-Graduação em Ciência da Computação |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/36705 |
Issue Date: | 18-Dec-2020 |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Dissertação Mestrado - Clynton Tomacheski.pdf | 1.78 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.