Hello Kulpreet, thank you a lot for your work, your post highlights some really interesting results.
I'm looking forward to your future work measuring the network's structure and decentralization. Moreover, I find thinking about the LN as a flow network to be a real interesting perspective. In fact, as an initial entry towards this direction, we did some work on a multi-path routing algorithm based on the push-relabel algorithm (cf. [1]). However, I think there is much room for improvement and other flow algorithms could turn out to be promising candidates for routing in the LN. As far as I understood, you would be using flow algorithms for a more in-depth analysis of the networks graph structure? Kind Regards, Elias [1]: https://arxiv.org/abs/1708.02419 On 29 Aug 2018, at 8:40, Kulpreet Singh wrote: > Hi René, > > Thanks for sharing the links to the issues and the excellent work you are > doing. > > I see that you are quite interested in helping autopilot create a > graph such that is provides certain characteristics. It is quite a > challenging task, and I admire your courage to take it on. I saw your > lib-autopilot too, though I didn't take a closer look at the code yet. > > I am focussing on a much simpler task of figuring out which metrics > the community will find useful and then trying to determine which > algorithms we could quickly run to get some initial results while we > try to develop more pertinent analysis algorithms. > > I focussed on betweeness centrality and articulation points as > personally I was most curious about those. Next I want to try and > figure out which max-flow algorithm might suit LN the best. Have you > looked at this? I might have missed something you might have already > pointed to. > > I noticed your concern about tracking articulation points. I agree, > that once central point dominance goes down the dependence on some > important articulation points will go down too. But as I noticed in my > results, some nodes are high in the list of articulation points sorted > by the number of atleast 5 node biconnected components they connect > to. But their centrality is not that high. For example, > mainnet.lightningconductor.net is in the list of top articulation > points but does not make it to the list of top 20 nodes by centrality. > > I am still curious about articulation points and want to keep tracking > it, who knows we might learn something interesting by tracking the > information. > > I am curious how are you running your graph evaluations. Are you using > python binding to BGL or python networkx? > > I imagine we got slightly different results also because we used data > from different times. I intend to publish the json output I got from > LND when I get around to plotting my results on a chart so we can > verify I am not making an error somewhere. > > Thanks and regards > Kulpreet > > > On Tue, 28 Aug 2018 at 00:31, René Pickhardt <r.pickha...@googlemail.com> > wrote: >> >> 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
smime.p7s
Description: S/MIME digital signature
_______________________________________________ Lightning-dev mailing list Lightning-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
