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
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
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.
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.