logo móvil
Contáctanos

Un algoritmo de Bellman-Ford para la distancia ponderada por la longitud del camino en grafos

Autores: Arnau, Roger; Calabuig, José M.; García-Raffi, Luis M.; Sánchez Pérez, Enrique A.; Sanjuan, Sergi

Idioma: Inglés

Editor: MDPI

Año: 2024

Descargar PDF

Acceso abierto

Artículo científico
2024

Un algoritmo de Bellman-Ford para la distancia ponderada por la longitud del camino en grafos


Categoría

Matemáticas

Subcategoría

Matemáticas generales

Palabras clave

Finito
Grafo dirigido
Distancia ponderada por la longitud del camino
Detección de fraudes
Fraude financiero
Vértices intermedios

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 34

Citaciones: Sin citaciones


Descripción
Consideremos un grafo dirigido finito sin ciclos en el que las flechas están ponderadas por pesos positivos. Presentamos un algoritmo para el cálculo de una nueva distancia, llamada distancia ponderada por la longitud del camino, que ha demostrado ser útil para el análisis de grafos en el contexto de la detección de fraudes. La idea es que la nueva distancia tiene en cuenta explícitamente el tamaño de los caminos en los cálculos. Tiene la característica distintiva de que, al calcularse a lo largo del mismo camino, puede resultar en una distancia más corta entre vértices muy alejados que entre los adyacentes. Esta propiedad puede ser particularmente útil para modelar escenarios donde las conexiones entre vértices están oscurecidas por numerosos vértices intermedios, como en casos de fraude financiero. Por ejemplo, para ocultar dinero sucio de las autoridades financieras, los estafadores a menudo utilizan múltiples instituciones, bancos e intermediarios entre la fuente del dinero y su destinatario final. Nuestra distancia serviría para hacer explícitas tales situaciones. Por lo tanto, aunque nuestro algoritmo se basa en argumentos similares a los que funcionan para los métodos de Bellman-Ford y Dijkstra, de hecho es esencialmente diferente, ya que la fórmula de cálculo contiene un peso que depende explícitamente del número de vértices intermedios. Este hecho condiciona totalmente el algoritmo, ya que los caminos más largos podrían proporcionar distancias más cortas, contrario a los algoritmos clásicos mencionados anteriormente. Presentamos el marco adecuado para su cálculo, mostrando las restricciones y requisitos para su uso, junto con algunos ejemplos ilustrativos.

Otros recursos que podrían interesarte

Temas Virtualpro