Lightning Network: Some Graph Theory Metrics — Part 1
Introduction
The Lightning Network is still advertised as an experimental technology and its viability as a 2nd layer solution for Bitcoin is yet to be proven. However, even in its experimental phase, the network has seen rapid growth since its mainnet release in January 2018, both in number of nodes/channels and in total capacity stored on it. Recently, the crypto currency exchange Bitfinex even announced it has activated lightning deposits and withdrawals on their exchange¹.
This article is the first of a series of articles aimed to analyse the Lightning Network using graph theory concepts. In this article, we will look at a set of graph metrics which can be used to monitor both the growth of the network and the health (eg: resilience) of its connections. The second article goes over the code to compute those metrics when running a Lightning Node, check it out here.
Note: if you want to get an idea of the current state of the network, all the metrics we will review below can be found on the BitcoinVisuals website.
Why the need for metrics?
A popular way of seeing the growth of the network has been through visualisation tools such as the ACINQ Lightning explorer² , 1ML’s visual representation³ or the LND Explorer⁴ seen below.
However, as the network gets larger, it has and will continue to be increasingly difficult to understand the network’s topology through visualisation. Indeed, our interpretation of such visualisations can be inherently flawed. It relies on our eyes making sense of what they see, and our eyes can be easily fooled by the disposition of the nodes in the visual representation of the network, as discussed in great detail by StopAndDecrypt in the following article:
Fortunately, there are other ways to analyse the structure of the Lightning Network thanks to the information that is publicly available to anyone running a lightning node and communicating with other peers. Running your own Lightning node gives you access to the network graph description, ie: information on the nodes and channels that compose the network if they are publicly visible.
This information can be summarised in a set of key metrics (which might be familiar to you if you studied graph theory) such as the diameter and radius of the graph, its transitivity, density (or completeness) and the number of cut edges and nodes that are in it. These are some of the properties that can be used to understand the network’s general structure and resilience or to describe the importance of a specific node or channel in it. Let’s define all of the above, and more, in the following section.
What are those metrics?
The Lightning Network’s goal is to function as a scalable payment layer for bitcoin. As such, it offers the opportunity to users to send funds to other users/services. In the network, a user is represented by a node and a payment is sent through a payment channel which correspond to a vertex and an edge in graph theory terms (we will use the terms interchangeably throughout the article). The two nodes don’t need to have a direct channel between themselves as they can communicate through one or more other nodes which form a route between them, also called a path.
It is common to refer to the total number of nodes/channels, or the total capacity held on the Lightning Network, to show how much it has grown over the past year. However, these metrics don’t tell us whether those new nodes and channels actually improved the usability of the network. Instead, we can use many other metrics to investigate the usefulness and importance of these nodes and channels. As someone who wants to contribute to the growth of the network, you can use those metrics to determine the overall health of the network as a payment system (or more generally as a routing system).
Before we dive into each of these metrics, you can already have a look at them on the BitcoinVisuals website over here. The first four (number of nodes, number of channels, network capacity and capacity per channel) as well as the last two (channels per node and capacity per node) are pretty self-explanatory and I will assume they do not need to be explained in this article. For the rest, let’s go over them one by one!
Distance Measures
Distance: in a graph, the distance between two vertices v and u is measured as the number of edges that form the shortest path from the vertex v to the vertex u. A path being a route between two vertices following along the edges of that graph.
Diameter: the diameter of a graph is the greatest distance connecting any two vertices in the graph.
Radius: the radius of a graph is the shortest greatest distance connecting any two vertices in the graph.
In the Lightning Network, the diameter represents the number of hops a transaction will have to do at most in order to route a transaction between two nodes (assuming it won’t need to backtrack because of insufficient funds or other). If we assume the shortest path calculation already takes into account the fees charged for routing and the capacity of each channel, then we should aim to minimise the diameter of the graph as more hops would mean more fees.
Completeness Measures
A graph is said to be complete if all the vertices that compose it are connected one to another. In other words, if all the vertices have an edge to all other vertices. This is best seen in a picture.
Density: the density of a (directed) graph is the ratio between the total number of edges in the graph and the maximum number of edges it could have. The formula is:
where E is the number of edges and V is the number of vertices.
In the Lightning Network, a very high density is unrealistic, and even unwanted. A density of 1 (ie: a complete graph) or close would require opening a channel with every node you wish to transact with. That would be a total waste of resources given the ability of the network to route payments. A very low density would also be unwanted as it would be representative of a low network resilience.
Indeed, concretely, a very low density means there are way more nodes than there are channels. This would occur either with the presence of large central routing hubs (vertices) or with long routing paths without alternatives. To determine which of the two is occurring, we would need to find the number of cut edges and cut vertices in the graph (see Connectivity Measures below)
However, a low density is not necessarily indicative of a weak network, other metrics need to be taken into account. In addition to that, the evolution of the network’s density (upwards or downwards) over time might be indicative of a healthy or unhealthy growth.
Clustering Measures
A cluster in a graph is a set of vertices, or subgraph, that are tightly inter-connected. Such clusters can be found by looking at the number of triangles, (also called closed triplets) present in the graph. A closed triplet is formed if a path of length 2 loops back to the first node of the triplet. If it doesn’t loop back it is called an open triplet as the triangle doesn’t close.
Transitivity: the transitivity ratio of a graph, also called global clustering coefficient, is the ratio between the number of closed triplets and the total number of triplets in the graph. Or, in other words, the number of triangles over the total number of possible triangles. It can also be computed for specific vertices. In that case it the ratio between the number of triangles of which the vertex is part and the total number of triangles it could be part of. We then talk about the local clustering coefficient.
In the Lightning Network, it would be unlikely to see a high graph transitivity ratio for the same reason it is unlikely to reach completeness, it would simply require too many channels. On the other hand, high vertex transitivity ratios allow us to find clusters in the network (tight interconnection between vertices in a neighbourhood). As an example, imagine a freelancing platform where a user can be both a buyer and a seller and where each user opens a channel with another user to sell/buy a service. There is a chance such a platform would form a cluster users paying each other fees for their respective service.
Connectivity Measures
A graph can be either connected or disconnected. It is said to be connected if for every two vertices in the graph, there exists a path between them. Equivalently it is said to be disconnected if for any two vertices in the graph, there is no path that connects them.
Cut vertex: a cut vertex is a vertex that, if removed from a connected graph, disconnects it into two connected components. They are sometimes also referred to as articulation points.
Cut edge: similarly, a cut edge is an edge that, if removed from a connected graph, disconnects it into two distinct connected components. They are sometimes referred to as bridges.
In the Lightning Network, cut vertices and cut edges can be seen as weak points of the network as their removal would entirely disconnect two parts of the network. Therefore, they should be minimised. This is especially true for cut nodes of high degree or cut channels a large capacity, as the network heavily relies on them for its good functioning.
Summary
In summary, this article outlines a range of metrics which are useful for anyone willing to monitor both the growth and the overall health of the Lightning Network. We briefly summarised the meaning of all these metrics and went over their concrete meaning in the context of the Lightning Network. If the size of the network keeps growing in the following months to years, it will become increasingly interesting, and important, to be able to monitor it without relying solely on visualisation tools. Even today, if you are willing to run a routing node and contribute to the network’s good functioning and resilience, the above metrics can be an important reference point to do smart channel management.
If you enjoyed this article or if you would like to discuss about its content don’t hesitate to leave a comment. You can also contact me through any of the platforms listed below. If you want the code to compute all the metrics seen here, check out the second part here. Until next time!
References
[1] Bitfinex Lightning Integration: https://www.bitfinex.com/posts/440
[2] ACINQ Lightning’s explorer: https://explorer.acinq.co
[3] 1ML Network representation: https://1ml.com/visual/network
[4] LND Explorer: https://graph.lndexplorer.com
Let’s socialise!
Don’t hesitate to contact me over any of the following platforms:
Twitter: @Stelios_Rms
Email: stelio.rammos@gmail.com
LinkedIn: https://www.linkedin.com/in/stelios-rammos-675382149/
My Lightning Node:
