L’algoritmo del ciclo di Floyd per il rilevamento di frodi nei sistemi Java

L’algoritmo di rilevamento del ciclo Floyd (Algoritmo di tartaruga e lepre) è un efficiente rilevamento del ciclo all’interno delle strutture iterative. Oltre agli elenchi collegati, è applicabile a problemi pratici come il rilevamento delle frodi e i flussi di lavoro degli utenti in cui i dati sono duplicati o ci sono dipendenze cicliche nei flussi di lavoro o nelle transazioni finanziarie.

Questo articolo illustra la sua pratica implementazione con un sistema di rilevamento fraudolento per le transazioni bancarie.

Caso d’uso: rilevare frodi nei trasferimenti di denaro

Una banca monitora regolarmente i trasferimenti di denaro tra i conti dei clienti. La frode può comportare cicli di denaro che scorre attraverso una serie di conti e tornare alla fonte (di solito per evitare il rilevamento o mascherare l’origine del denaro). Identificando questi cicli, le banche possono essere avvertite di possibili azioni di riciclaggio.

Dati di esempio per questo esempio:

Comprendere i dati che sono stati campionati

1. Trasferimento dal conto “ABC” al conto “BCD”.
2. Dall’account “BCD” all’account “CDE”.
3. Infine, “CDE” invia a “def”.
4. Passando dall’account “def” per l’account “BCD” crea un ciclo: BCD → CDE → Def → BCD.

Come utilizzare l’algoritmo per il rilevamento

Nell’implementazione del rilevamento del ciclo mediante l’algoritmo di Floyd, le transazioni sono modellate come un grafico diretto in cui:

1. I nodi rappresentano account
2. I bordi rappresentano i trasferimenti di denaro tra i singoli nodi

Ci sono due puntatori (puntatori lenti e veloci) usati per verificare i cicli/loop.

Mappatura degli oggetti Java Mappatura del trasferimento dell’account:

class AccountTransferGraph {
    personal last Map> adjacencyMap=new HashMap();
    //add a switch from one account to a different
    public void addAccountTransfer(String supply,String vacation spot){
        adjacencyMap.computeIfAbsent(supply, ok -> new ArrayList()).add(vacation spot);
    }
    //retrieve all transfers from a given account
    public Checklist getTransfers(String account){
        return adjacencyMap.getOrDefault(account,new ArrayList());
    }
    //retrieve all accounts
    public Set getAllAccounts(){
        return adjacencyMap.keySet();
    }
}

Classe Helper per trovare cicli dal grafico creato usando Oggetto Java sopra:

class FloydCycleDetector{
   public static boolean isCyclePresent(AccountTransferGraph graph,String begin){
       String sluggish=begin,quick=begin;
       whereas(true){
           // Transfer sluggish pointer one step
           sluggish = subsequent(graph, sluggish);

           // Transfer quick pointer two steps
           quick = subsequent(graph, subsequent(graph, quick));

           // If pointers meet, a cycle is detected
           if (sluggish != null && sluggish.equals(quick)) {
               return true;
           }

           // If quick pointer reaches null, no cycle exists
           if (quick == null || sluggish == null) {
               return false;
           }

       }
   }
    // get subsequent account
    personal static String subsequent(AccountTransferGraph graph, String account) {
        Checklist transfers = graph.getTransfers(account);
        return transfers.isEmpty() ? null : transfers.get(0);
    }

}

Classe di prova per convalidare la logica sopra:

// Primary class to check the algorithm
public class FraudDetectionSystem {
    public static void most important(String() args) {
        //STEP 1: Construct the account switch graph object
        AccountTransferGraph graph = new AccountTransferGraph();

        //STEP 2: add check account switch information
        graph.addAccountTransfer("a", "b");
        graph.addAccountTransfer("b", "c");
        graph.addAccountTransfer("c", "d");
        graph.addAccountTransfer("d", "b");

        //STEP 3: verify for cycles ranging from every account
        for (String account : graph.getAllAccounts()) {
            if (FloydCycleDetector.isCyclePresent(graph, account)) {
                System.out.println("Cycle detected ranging from account: " + account);
                return;
            }
        }
        System.out.println("No cycles detected.");
    }
}

Spiegazione del codice

IL AccountTransferGraph La classe rappresenta le relazioni tra gli account come grafico diretto. Ecco alcuni dei suoi metodi:

• addAcountTransfer(String supply, String vacation spot) – Aggiunge un trasferimento (bordo diretto) tra due account
• getTransfers(String account) – recupera un elenco di conti a cui un account specifico ha trasferito denaro
•  getAllAccounts() – restituisce tutti gli account (nodi) nel grafico

Algoritmo di rilevamento del ciclo di Floyd

IL FloydCycleDetector La classe usa due puntatori:

• Puntatore lento (tartaruga) – Va una posizione alla volta.
• Puntatore veloce (Hare) – Va due posizioni alla volta.

Comportamento dell’algoritmo:

1. Se un ciclo è presente nel grafico:
   • Il puntatore lento, che si muove a un ritmo costante, alla high quality incontra il puntatore veloce advert un certo punto.
2. Se non è presente alcun ciclo/loop:
   • Uno dei puntatori del programma attraversa fino alla high quality (null).

Metodo chiave

IL isCyclePresent(AccountTransferGraph graph, String begin) Il metodo è progettato per:

• Rileva se c’è un ciclo a partire dal conto dato
• Usa il metodo Helper subsequent() per recuperare il prossimo account nella catena

Classe di prova per convalidare l’algoritmo di cui sopra nel rilevamento delle frodi.

IL FraudDetectionSystem La classe integra il accountTransferGraphe logica di rilevamento del ciclo:

1. Costruisce il grafico con i trasferimenti
2. Controlla ogni account nel grafico per i cicli utilizzando l’algoritmo di Floyd
3. Risultati Se viene rilevato un ciclo

Limitazioni e possibili miglioramenti

• Rilevazione di singoli cicli. L’algoritmo di Floyd identifica un ciclo. La prima ricerca di profondità (DFS) dovrebbe essere utilizzata in tutti i casi per identificarli tutti.
• Grafici complessi. L’algoritmo presuppone un bordo per nodo. Per i grafici con bordi multipli, potrebbe essere necessario un certo adattamento.

Uso versatile dell’algoritmo di rilevamento del ciclo di Floyd

Ciò è molto popolare nel fornire il rilevamento del ciclo in elenchi e grafici collegati per un’efficace gestione della memoria ed evitare un ciclo infinito negli algoritmi. In networking, identifica i loop di routing e ottimizza un modello di sistema distribuito che evita i impasse. Nella bioinformatica, aiuta advert analizzare le sequenze di DNA e le simulazioni della struttura proteica identificando modelli ripetuti all’interno di dati biologici complessi.

È anche usato in AI e ML per impedire che si verifichino i loop di allenamento Apprendimento del rinforzo o per identificare le dipendenze cicliche nei modelli basati su grafici. In blockchain, sistemi operativi o crittografia, l’algoritmo di Floyd continua a essere un vantaggio per fornire stabilità ed efficienza in diversi regni di calcolo.

Conclusione

L’algoritmo di rilevamento del ciclo di Floyd è una soluzione semplice ed efficace ai problemi del mondo reale che coinvolgono la struttura ciclica. Nell’esempio sopra, la sua applicazione al rilevamento di frodi bancarie implica che può essere utile in altri casi d’uso. L’algoritmo può essere integrato nei sistemi a vari livelli per migliorare l’integrità operativa e l’efficienza grazie alla sua semplicità ed efficienza.

Il codice di esempio sopra è presente in Repository github.

Maggiori dettagli sull’algoritmo di cui sopra sono disponibili Geeksforgeeks. IL Sanfoundry Mostra l’integrazione dell’algoritmo di rilevamento del ciclo FLOYD nelle applicazioni Java.