Kulpreet Singh [ARCHIVE] on Nostr: 📅 Original date posted:2018-08-29 📝 Original message: Hi René, Thanks for ...
đź“… Original date posted:2018-08-29
đź“ť Original message:
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
đź“ť Original message:
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