The Lightning Network is a scale-free network. This paper is tangentially related, and the algorithm it describes could be used to alleviate some of the centrality issues of LN that have been identified.
I think I will start regularly posting synopsis/takeaways. But I'll have to start linking to another website because I need to include pictures (foreshadowing). If you have any papers you would to see summarized, feel free to message me here or on twitter. Comments/question welcomed as well.
Abbas SM, Javaid N, Azar AT, Qasim U, Khan ZA, Aslam S. Towards Enhancing the Robustness of Scale-Free IoT Networks by an Intelligent Rewiring Mechanism. Sensors (Basel). 2022 Mar 30;22(7):2658. doi: 10.3390/s22072658. PMID: 35408272; PMCID: PMC9003452.
Towards Enhancing the Robustness of Scale-Free IoT Networks by an Intelligent Rewiring Mechanism
Summary This paper studies how the robustness of scale-free networks can be improved against random and malicious attacks. Scale-free network are vulnerable to attacks that target central nodes in the network. In particular, the researchers show that closeness centrality (a measurement that describes the distance a node is from all other nodes in the network) is a useful, efficient way to identify nodes to attack. As a result, they propose the Intelligent Rewiring (INTR) mechanism to mitigate the effects of a centrality based attack.
Robustness is defined as how well a network maintains connectivity during an attack. Calculating robustness involves incrementally simulating larger attacks on the network. In the paper, robustness is quantified as a summation from 0 to the number of nodes-1. Each term in this summation is a fraction that describes how disconnected the network becomes after removing the $i$ nodes with highest closeness centrality. That fraction is the size of the largest connected component after the attack divided by the total number of nodes in the network. A fraction closer to 1 indicates that few nodes were disconnected while a value closer to 0 indicates many nodes were disconnected. Therefore, a higher robustness value indicates a network that stays connected even as a larger number of central nodes are removed.
The INTR mechanism selects nodes to rewire based on their degree. It selects 4 nodes: the highest degree node (i) and its lowest degree neighbor (j), and the second highest degree node (k) and its lowest degree neighbor (l). Then, the algorithm adds 2 random edges among these nodes and calculates the new robustness. If the resulting robustness increases, the rewiring is kept. Otherwise a different rewiring is tried. This entire process is repeated n times where n is the number of nodes in the network.
The performance of this algorithm is compared against state of the art rewiring algorithms on scale-free networks generated using the Barabasi-Albert model. This model creates scale-free network with the characteristic power law degree distribution i.e. there are many nodes with low degree and few nodes with high degree. In comparison against existing algorithm, SA and ROSE, INTR outperformed in improving robustness of scale-free network.
Strengths
  • Explanations of the attacks, network metrics and algorithms were very clear.
  • Included a table of limitations, solutions, and validations.
Weakenesses
  • The psuedocode for algorithm 4 differs from its explanation in lines 8-12. The authors do not show psuedocode that defines what happens if the robustness does not increase from the rewiring.
  • The scope is too broad. The HDLA and RHDLA (not mentioned in the takeaway) could have been excluded entirely.
Possible extensions
  • I would be interested in adapting this rewiring procedure to be an attachment strategy for the Lightning Network. Instead of randomly rewiring edges between nodes, connect all the independent nodes to a joining node, and measure robustness.
Question/corrections welcome!
As there is no central coordination in Lightning, how might we encourage such rewiring? It seems like we'd need to incentivize "wires" that exist for the sake of robustness, but perhaps don't actually route payments. It seems like we have a hub and spoke topology because the network's incentives favor it.
reply
Lovely question! Check out the explanation to algorithm 4 in the paper, I'm not sure I explained it well enough in the writeup.
You are right, nodes are only capable of opening channels between themselves and someone else, so this algorithm would have to be adapted. The algorithm selects 4 nodes according to some properties. Then the easiest modification would be to open channels with them to a fifth node (your node).
Another idea is to just insert yourself as one of the 4 nodes. You could do this artificially (replace one of the four with yourself at random), or you could exclude candidate nodes from the algorithm. By excluding nodes with a greater degree than you, you would become node i in the algorithm. Then just keep the actual channels you can open.
Robustness tells us how well a network can maintain service when nodes become unavailable (failure/attack/liquidity). Using the method from the paper should distribute closeness centrality and improve path diversity between nodes. But you're right, I don't think people are necessarily incentivized to open channels in this way, it's more of an altruistic strategy.
It would be interesting to see how well the robustness of LN could be improved by a limited number of rewirings.
reply