René Pickhardt [ARCHIVE] on Nostr: 📅 Original date posted:2018-08-27 📝 Original message: Hey Kulpreet, thanks for ...
📅 Original date posted:2018-08-27
📝 Original message:
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180828/83b36302/attachment-0001.html>;
📝 Original message:
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180828/83b36302/attachment-0001.html>;