Graph Theory!

Alright, here we go, exciting days.

SO, in my last blog post, I explained what arbitrage in forex markets is and left off by saying that in this one I was gonna explain how graph theory can be used to find these opportunities, so that’s the plan for today. You don’t really need to go back and read the last one to get what I’m doing here, but I certainly encourage you to if you want a better picture of the larger project that I’m working on here.

To recap from the last blog. A graph is a collection of points (called nodes) that are connected by edges. It looks like this:

You’ll notice in the picture above that some of the edges are highlighted in a pattern that seems to form a loop. This loop is called a cycle, and it’s defined as a walk between nodes that ends at the node it started and only crosses each other node one time.

If we wanted to represent these graphs in a more mathematically applicable way, we could use an ‘adjacency matrix’ to represent the connections between nodes. The adjacency matrix of this graph is shown below.

As you can see, each row and column represents a given node and the connections between the nodes are expressed as 1’s at the intersection of connected nodes rows/columns. There are a lot of important features that could be discussed about this matrix, but for the sake of brevity, the important takeaway is that we can represent a pictorial graph using this mathematical structure.

With this setup established, we can begin to start thinking about money again. Let’s say instead of identifying each node with a number, I wanted to give them each a currency label. Now we would have a graph that looks like:

With this graph, we can start thinking about the movement between nodes in a more advanced way. For example, this cycle would represent the exchange of currencies going from USD -> EUR -> JPY -> CAD -> USD:

Now that we’ve represented a conceptual exchange of currencies, we can start to think about implementing the exchange rates between the currencies to find arbitrage opportunities. To do this, we come back to the adjacency matrix, but this time instead of filling out each intersection with a 1 or a 0 depending on whether or not the nodes are connected [1], we can use the exchange rates between the currencies to represent a movement from one node on the graph to another.

[2]

If you just glance at this matrix, it’s definitely very unclear what anything means, but if you look closely at the trade from USD -> EUR and then EUR -> USD you can see that it’s approximately (the values are rounded, I did this in Microsoft paint) the inverses of one another. The numbers being inverses means that if you run your money through the cycle USD -> EUR -> USD, you would end up with the same amount as you started. But this isn’t true for all the cycles you could possibly run, behind the obfuscation of numbers there is a present arbitrage opportunity in this matrix. If you run the cycle GBP -> CAD -> JPY -> GBP, you would multiply your money by a factor of 1.0002. This may seem like a small amount (or even just completely meaningless when working with numbers as rounded as I have them, I’ll use more precise measurements in the future), but if you were to do this 100 times you could find significant profits.

With this, we finally have all of the tools and knowledge together to start working on the algorithms necessary to find arbitrage opportunities in this mess of numbers. Next week I’ll explain those algorithms, and then the week after that I’m hoping to show my code for the idealized simulation, and then maybe after that I’ll try and derive some proofs about real-world trades or something.

[1] Doing this would be redundant because each node connects to every other except itself.

[2] This specific example is taken from the paper “Tropical algebra, graph theory, & foreign exchange arbitrage” don’t give me a zero for the course please, I needed to read about this before I could make my own stuff and its easier to use existing examples