A Bellman-Ford algorithm for the path-length-weighted distance in graphs
R. Arnau, J. M. Calabuig, L. M. García Raffi, E. A. Sánchez Pérez, S. Sanjuan · 2024
Read A Bellman-Ford algorithm for the path-length-weighted distance in graphs by R. Arnau, J. M. Calabuig, L. M. García Raffi, E. A. Sánchez Pérez, S. Sanjuan (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-00819.txt.
Description
Abstract . Consider a finite directed graph without cycles in which the arrows are weighted. We present an algorithm for the computation of a new distance, called path-length-weighted distance, which has proven useful for graph analysis in the context of fraud detection.
Catalog record
| CREATOR | R. Arnau, J. M. Calabuig, L. M. García Raffi, E. A. Sánchez Pérez, S. Sanjuan |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-00819
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Bellman-Ford algorithm for the path-length-weighted distance in graphs R. Arnau, J. M. Calabuig, L. M. García Raffi, E. A. Sánchez Pérez, S. Sanjuan Abstract . Consider a finite directed graph without cycles in which the arrows are weighted. We present an algorithm for the computation of a new distance, called path-length-weighted distance, which has proven useful for graph analysis in the context of fraud detection. The idea is that the new distance explicitly takes into account the size of the paths in the calculations. Thus, although our algorithm is based on arguments similar to those at work for the Bellman-Ford and Dijkstra methods, it is in fact essentially different. We lay out the appropriate framework for its computation, showing the constraints and requirements for its use, along with some illustrative examples. 1991 Mathematics Subject Classification Primary: 05C38; Secondary: 90C35 1. Introduction Algorithms for calculating the (weighted) path-distance between vertices in a graph appeared in the middle of the 20th century, motivated by the growing interest of the time in the applications of mathematical analysis of graphs. The Bellman-Ford algorithm is the main reference of these early studies [ 2 ] . Dijkstra’s algorithm for solving the same problem appeared at about the same time [ 11 ] , and differs from the other, being more efficient depending on the particular problem. After these original works, the growing interest in the subject (due to the numerous applications that graph theory has found in many fields) has given rise to a great deal of research on graph analysis, which often includes the study of these structures when considered as metric spaces. The idea of considering a graph also as a metric space goes back to the beginnings of the theory of graphs. Metric notions begin to appear explicitly in mathematical works in the second half of the last century. The main metric that was considered (and in a sense the only one until the latter part of the century) was the so-called path distance ( [ 12 , 15 , 18 ] ): for undirected and connected graphs, this metric evaluated between two vertices (nodes) is defined as the length of the shortest path between them (see for example [ 4 , §.2.2.2] ). One of the first advances in the metric analysis of graphs was the introduction of weights in the definition of the path distance, assigning weights to the individual paths connecting two consecutive nodes and calculating the infimum of the sum of these weights. Some recent papers on the subject using weighted distances that have inspired this paper are [ 8 , 14 ] . As in the case of other notions of fundamental graph theory, the relevant theoretical ideas appeared together with research topics from other scientific fields, such as sociology [ 1 , 16 , 22 ] . The definition of different metrics and algorithms to compute them increased greatly in the last decade of the last century, often proposed by problems from other disciplines such as chemistry or crystallography (see [ 18 , 19 ] and references therein). In this sense, there is a particular case that deserves attention, that is the resistance distance [ 9 , 23 ] . Coming from some ideas in theoretical chemistry [ 19 ] and social network analysis [ 22 ] , this definition turned out to be a useful tool in the study of molecular configurations in chemistry, although it has also been used in network analysis and other fields [ 24 , 5 , 3 ] . In general, metrics could play a relevant role when studying properties such as robustness (see for example the survey [ 21 ] ; see also [ 20 ] ). The interested reader can find more information on applications of metric graphs in the books [ 6 , 4 , 13 ] . In the same direction, in this paper we provide an algorithm to compute a new distance that also appeared in an applied context, in connection with the automatic analysis of fraud in economic networks (see [ 7 ] ). In this paper, we show that this metric allows to consider vertices that are far away when the distance is measured using the path-distance, becoming close with respect to this metric. It is especially useful in the economic analysis of fraud in networks of companies, since very often the strategy used to hide such fraud is to use the path-distance. Technically, it is defined as a weighted metric, but by dividing the sums of weights appearing in the infimum that provides the value of the metric by a new term that depends on the number of steps involved in the summation. We will show that this change in the weighting process forces to radically change the algorithm to calculate it, since in this new case, longer paths could give shorter distances. However, in the present work we consider the case of acyclic directed graphs, in order to avoid restrictions that make it impossible to define a weighted path metric, since continuous passage through a cycle could always give a null value to the metric (which would mean that it is not a metric). There are other ways to avoid this (see for example Proposition 4.1 in [ 7 ] ), but in our case we decided to compute the distance between vertices by restricting the set of possible paths in the infimum that gives it. The way to do this is to avoid cycles, and to consider directed graphs. As a result, what we compute is not a metric on the whole graph, but only a distance between two vertices chosen in it. Let us give now some basic definitions about graphs and metric spaces. Let us explain some concepts related to the general definition of what a metric is, which will adapted later to the graph theoretic framework. Let \mathbb{R}^{+} be the non-negative real numbers. An (extended) quasi-metric on a set \Omega is a function d:\Omega\times\Omega\to\mathbb{R}^{+}\cup\{\infty\} such that for all a,b,c\in\Omega , the axioms (1) d(a,b)=0=d(b,a) if and only if a=b, and (2) d(a,b)\leq d(a,c)+d(c,b) hold. The resulting quasi-metric structure (\Omega,d) is called a quasi-metric space. For the specific framework of this paper, a useful summary of the notions of distance in graphs, with sufficient explanation and many examples, is given in Chapter 15 in [ 10 ] . In this paper we will deal with the so called path-length-weighted distance, that was introduced in [ 7 , §.4] . It should be noted that the version defined there is given for non-directed graphs, and so the definition we will use is slightly different. However, we will define an extended quasi-metric also in this case by giving the value d(a,b)=\infty when there is no path for going from a to b, and considering only allowed paths between vertices. Since we are interested in how to compute the distance, and not in theoretical questions about its metric space structure, we will focus attention on the computational algorithm. All the notions on graph theory that are needed can be found in books on this subject, as for example [ 4 ] . We will introduce some of them in the