Algoritmos para o problema de nilcatenation com aplicação na detecção de lavagem de dinheiro em criptomoedas

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.