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!