Paper Synopsis: Can Lightning Network’s Autopilot Function Use BA Model as the Underlying Network?
This is a brief summary of the paper Can Lightning Network’s Autopilot Function Use BA Model as the Underlying Network? by Zhen Wang, Rui Zhang, Yipeng Sun, Hong Ding and Qiuyun Lv*.
Substack is much better for editing these kinds of posts, but I will try to communicate on stacker.news or twitter if you have any questions/comments.
Summary
The Barabasi-Albert model is used in designing Lightning Network routing protocols, simulating transactions, and evaluating robustness. As the network grows popularity, it will become advantageous to automatically establish new channels with other nodes. (autopilot, clboss, surge, etc.) This work investigates whether the BA model is representative of the Lightning Network in evaluating new protocols, etc.
Data Collection
The researchers collected network data from https://ln.bigsun.xyz/, an LN Directory. This data was collected from the beginning of the Lightning Network, Jan. 12th, 2018 to April 20th, 2021. Over that time, there were ~150,000 and ~40,000 unique channels and nodes observed, respectively. Similar to the first paper synopsis I posted online, these researchers were able to recreate snapshots of the network by replaying data collected from the directory. They have 12 snapshots, one for each 100 day interval of data collected. These snapshots were then compared to BA graphs of similar size.
There are 3 distinct stages that can be observed in this graph:
Start-Up period [0-300] - slow growth of nodes and channels
Outbreak period [300-450] - accelerated growth, number of channels quadrupled
Cooling-Off period [450-1200] - network is over resourced, channels decrease and stabilize.
The researchers remark that the growth and cooling off may have been influenced by price. They hint at an equilibrium between supply and demand of liquidity on the network being found around day 600.
One should do their own research on Barabasi-Albert graphs which are a method for generating scale-free networks. But here are the highlights:
Power law degree distribution - there are many nodes with few connections and few nodes with many connections. The relationship between the number of nodes with some degree k decreases exponentially as k increases.
Small Diameter - even with graphs of 1000+ nodes, the longest shortest path in the network is low. For example, even with thousands of airports, one can reach most destinations in 2-3 layovers.
Neutral Assortativity - assortativity describes the likeliness of nodes to connect to other nodes with similar degree as themselves. How likely are high degree nodes to connect to low degree nodes versus other high degree nodes? BA models are only slightly disassortative, meaning there is a slight bias for nodes with different degrees to connect, but the trend is mostly indiscernible.
Preferential attachment to Degree - Joining nodes are more likely to create edges to nodes in the network with high degree. The rich get richer, resulting in a power law degree distribution, as mentioned earlier.
These are the four metrics by which the researchers used to compare snapshots of LN to BA graphs of similar size.
Power Law Degree Distribution
Here are the degree distributions of the last 3 snapshots of the network, fitted to power laws. The scales are logarithmic, and it can be seen that there is a downward linear trend line. The authors also included the error of the fitting, and showed that it decreased from 10% error to 3% over the course of the study.
Conclusion: The Lightning Network has a power law degree distribution.
Assortativity
Here is the assortativity of the Lightning Network (unfortunately, in blue) compared to the assortativity of a similarly-sized BA model (orange). The Lightning Network exhibits high disassortivity, which is intuitive given that many nodes are user nodes with few channels. These nodes are more likely to connect to well connected nodes than to ill-connected nodes. On the other hand, BA models exhibit a neutral assortativity.
Conclusion: The Lightning Network does not exhibit the same assortativity as the BA model.
Diameter
This ones a little less interesting. The diameter of the Lightning Network is about twice that of a similarly sized BA model. This is true even after removing all nodes with a single channel.
Conclusion: The Lightning Network does not exhibit the same diameter as the BA model.
Preferential Attachment
If the BA model is representative of the Lightning Network, one would expect to see a preferential attachment of joining nodes to high degree nodes in the network, as it grows. The researchers tracked new nodes entering the network from days 600-1100 and to which nodes they opened channels with.
They plotted the distribution of degree/betweenness/closeness centralities of the nodes that the joining nodes chose to open channels with. They found that nodes open channels with preference to closeness centrality, in effect minimizing their cost to use the network. This differs from BA models, where nodes open channels with preference to high degree nodes.
Conclusion: The Lightning Network does not have a preferential attachment to high degree nodes, like the BA model.
Final Conclusion
While the Lightning Network follows a power law degree distribution, the BA model is not representative of LN.
LN is disassortative while BA is nearly neutral.
LN has a larger diameter even after removing tandem nodes.
LN follows a closeness-preferential attachment while BA follows a degree-preferential attachment.
Therefore, the BA model should not be used as a substrate model of the Lightning Network.
Strengths
Huge collection of network data, starting from the Lightning Networks inception.
Good data visualization, thorough network analysis, included tables with graphs.
Weaknesses
Several typos, the typo in figure 6 could confuse the conclusion.
Authors used a website to gather data about the network instead of collecting it themselves. This website is no longer available.
Potential Research Question
If LN follows a closeness-preferential attachment, are there ways of generating graphs with this attachment? Are they a good substrate network?
P.S. Ask me what model I think should be used instead :-)
Technical corrections preferred!