Hey Kulpreet, thanks for this nice overview article! I have just today implemented a first draft for the c-lightning autopilot [0]. I have implemented 4 heuristics to select nodes to which one could connect. On of those [1] samples from the nodes that contribute to the high diameter. This heuristic was included not to increase the utility of the node that is running the autopilot but to improve the network properties. I believe that this heuristic should also reduce the articulation points and biconnected components that you mention in your article. As endpoints of longest shortest paths will most likely be in two different biconnectivity components (at least if those exist and have a certain size).
Regarding the centrality. I also calculated the betweeness centrality and have similar results [2] to yours. I guess the difference will be due to the fact that we don't work on the exact same snapshot. My autopilot implementation also connects to a few rather central nodes. I doubt this is useful for the network but I guess it is good for the node running the autopilot since it gains access to many nodes. ( Actually I think - but don't know - that in combination with [1] it even helps the network). Regarding your 200 Articulation points I would guess that many of those are just nodes that only have one channel with the node that acts as an articulation point. I guess this is not something that we would need to take care of so much since it is also in the responsibility of those nodes to have more than one channel. for larger biconnectivity components the problem would probably be resolved with the above mentioned heuristic. Therefor I believe looking at the articulation points should not be our main focus. Something that (regarding the autopilot) I am currently missing in your article is how much funds should be allocated for the suggested channels. I am currently experimenting with a probability density function that is proportional to the average capacity of each node in the candidate set. I smooth this with a uniform distribution. However simulations at this point are quite expensive (if done primitively since the centralities have to be recomputed) I guess this would be a nice future work. I will probably tomorrow publish the rest of the code for the lib-autopilot that uses this heuristic for channel balances since I am currently still working on it. If you consider working more on the autopilot but also on research related to this I would also suggest the following resources [3],[4] and [5] [0] https://github.com/ElementsProject/lightning/pull/1888 [1] https://github.com/renepickhardt/lightning/blob/8c91f57490b51f772513a274d679d3ab62e7201a/contrib/lib-autopilot.py#L205 [2] https://twitter.com/renepickhardt/status/1034066602273193985 [3] https://github.com/lightningnetwork/lnd/issues/677 [4] https://github.com/renepickhardt/Automatically-Generating-a-Robust-Topology-for-the-Lightning-Network-on-top-of-Bitcoin [5] https://www.rene-pickhardt.de/improve-the-autopilot-of-bitcoins-lightning-network-summary-of-the-bar-camp-session-at-the-2nd-lightninghackday-in-berlin/ best regards Rene On Mon, Aug 27, 2018 at 11:59 PM Kulpreet Singh <zapfm...@gmail.com> wrote: > Hi all, > > I have been thinking about how we could measure the centrality of > various nodes in the LN graph and the dependence on some nodes to > route payments and to prevent network partitions. I think measuring > and tracking the changes in key metrics could help the community > decide on which nodes to open new channels with. > > I measured the centrality of nodes and the central point dominance as > defined in the seminal paper by Lindon C. Freeman, "A Set of Measures > of Centrality Based on Betweenness", Sociometry 40, pp. 35-41, 1977. > > I also measured the number of articulation points in the network as > per Robert E. Tarjan, "Depth first search and linear graph algorithms" > SIAM Journal on Computing, 1(2):146-160, 1972. > > I want to add, that this is just a start, I understand that we should > probably look at treating LN as a directed graph and that we should do > some work in trying to do some analysis based on treating LN as a flow > network. > > However, I am eager to share my early results and would welcome any > feedback or suggestions on the way forward. > > I wrote a medium post describing the approach and show my results > there. I also elaborate on the choice of the two metrics and what they > mean for LN. The post is available here: > > https://medium.com/@jungly/measuring-node-centrality-in-lightning-network-8102a59999f0 > > Looking forward to your suggestions and feedback. > > Thanks > Kulpreet > _______________________________________________ > Lightning-dev mailing list > Lightning-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev > -- https://www.rene-pickhardt.de Skype: rene.pickhardt mobile: +49 (0)176 5762 3618
_______________________________________________ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
