Elias Rohrer [ARCHIVE] on Nostr: 📅 Original date posted:2018-08-29 📝 Original message: Hello Kulpreet, thank you ...
📅 Original date posted:2018-08-29
📝 Original message:
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.pickhardt at 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 <zapfmann at 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 at 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180829/3c71f054/attachment-0001.html>;
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4970 bytes
Desc: S/MIME digital signature
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180829/3c71f054/attachment-0001.p7s>;
📝 Original message:
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.pickhardt at 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 <zapfmann at 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 at 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180829/3c71f054/attachment-0001.html>;
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4970 bytes
Desc: S/MIME digital signature
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180829/3c71f054/attachment-0001.p7s>;