Re: [Lightning-dev] Measuring centrality of nodes in LN graph
Hello Kulpreet, Thank you for the interest in our work! wrt. 1.: You are correct, message complexity could be one of the main challenges in the distributed case (~ O(n^3) in the asynchronous model, according to Goldberg et al.). While this is clearly unfeasible to run for every single payment, ideas like introducing rounds or batching payments could help with that. However, you are absolutely right that a lot more work would be needed to find an optimized distributed solution with feasible overhead. wrt. 2.: Yes, replacing the route selection algorithm of the current source routing scheme with a flow-based approach should be possible and would be interesting to see. In particular, I would find it especially promising to combine such a flow-based approach with the atomic multi-path payment (AMP) scheme that was proposed in the beginning of this year. So far, I have not looked into possible library candidates for a prototype implementation in the Go client. But maybe I should, as it seems exiting (now that I'm thinking about it ;)). Ah, nice! I think, as a first idea, it could be enlightening (no pun intended) to even have a look at (average) maximum flows between all or random nodes. This could help to understand how much payment capacity can be unlocked by implementing a multi-path approach, such as AMP. Thanks & Best Regards, Elias On 13 Sep 2018, at 14:55, Kulpreet Singh wrote: > Hi Elias, > > Thanks for the pointer to your excellent paper. I really enjoyed > reading the idea of using locked flows to allow for a distributed > execution for finding valid flows, which will enable discovering > routes for payments. Pretty neat idea indeed. > > I just have few questions. My understanding might be incorrect and > therefore I ask. > > 1. The distributed execution as proposed in the Goldberg paper > requires a number of nodes to communicate with each other, essentially > nodes are talking to their neighbours, but I imagine this results in a > waterfall eventually as nodes talk their neighbours and so on. How do > you see this working practically? Do you envision periodic route > calculation phases, where all routing nodes collaborate even x seconds > to help find routes for all the payments in that phase? This might > result in the "instant payment" property of LN suffering a bit. I hope > I understood the Goldberg approach and my question isn't completely > off the hook. > > 2. If we leave the distributed execution aside for a moment and try > the "feasible flow" approach from your paper and compare that to the > current implementation in LN for route calculation, it might make for > an interesting result. So the question is, do you have an > implementation of the push-relable algorithm in Go that could be tried > out in LN? Or have you see one as part of another lib? > > About my work to observe LN metrics, I was hoping to see if there were > any metrics from the network flow literature that might be relevant to > LN. Do you think any specific one might be interesting to track? > > Thanks again for sharing your paper > > Kulpreet > On Wed, 29 Aug 2018 at 11:45, Elias Rohrer wrote: >> >> 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 >> >> 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
Re: [Lightning-dev] Measuring centrality of nodes in LN graph
Hi Elias, Thanks for the pointer to your excellent paper. I really enjoyed reading the idea of using locked flows to allow for a distributed execution for finding valid flows, which will enable discovering routes for payments. Pretty neat idea indeed. I just have few questions. My understanding might be incorrect and therefore I ask. 1. The distributed execution as proposed in the Goldberg paper requires a number of nodes to communicate with each other, essentially nodes are talking to their neighbours, but I imagine this results in a waterfall eventually as nodes talk their neighbours and so on. How do you see this working practically? Do you envision periodic route calculation phases, where all routing nodes collaborate even x seconds to help find routes for all the payments in that phase? This might result in the "instant payment" property of LN suffering a bit. I hope I understood the Goldberg approach and my question isn't completely off the hook. 2. If we leave the distributed execution aside for a moment and try the "feasible flow" approach from your paper and compare that to the current implementation in LN for route calculation, it might make for an interesting result. So the question is, do you have an implementation of the push-relable algorithm in Go that could be tried out in LN? Or have you see one as part of another lib? About my work to observe LN metrics, I was hoping to see if there were any metrics from the network flow literature that might be relevant to LN. Do you think any specific one might be interesting to track? Thanks again for sharing your paper Kulpreet On Wed, 29 Aug 2018 at 11:45, Elias Rohrer wrote: > > 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 > > 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 > 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
Re: [Lightning-dev] Measuring centrality of nodes in LN graph
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 > 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
Re: [Lightning-dev] Measuring centrality of nodes in LN graph
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 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]
Re: [Lightning-dev] Measuring centrality of nodes in LN graph
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 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-8102a5f0 > > 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
[Lightning-dev] Measuring centrality of nodes in LN graph
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-8102a5f0 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
