Timeline for Efficient algorithm for Wasserstein-1 distance in graph setting
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 21, 2017 at 14:01 | comment | added | Igor Rivin | @Thomas glad it helped! | |
| Sep 21, 2017 at 10:49 | comment | added | JustSomeGuy | So thank you @IgorRivin, you've just made my life a whole lot easier! | |
| Sep 21, 2017 at 10:48 | vote | accept | JustSomeGuy | ||
| Sep 21, 2017 at 10:48 | comment | added | JustSomeGuy | For a single realization of the SBM with the same parameters, it takes about 25 second to calculate all the Wasserstein-1 distances for the shortlist method, while it takes 51 and 117 seconds for the LP and flow implementations. The difference grows even larger for bigger graphs, while it decreases for smaller graphs (due to my parallel implementation I suspect) | |
| Sep 21, 2017 at 10:46 | comment | added | JustSomeGuy | Just for comparison's sake: calculating one Wasserstein-1 distance for the averaged stochastic block model with 2 blocks of 250 vertices each with parameters $p_{in} = 0.12$ and $p_{out} = 0.1$ takes about 0.13 seconds with the shortlist method, while it takes about 3.22 and 3.27 second with my LP and flow implementations. | |
| Sep 21, 2017 at 10:43 | comment | added | JustSomeGuy | The funny thing is that I already tried the R package supplied by the authors when it appeared a few months ago, but I missed the 'shortlist' option with the algorithms they provided. Having read this paper I tried that option, and the results are astounding! | |
| Sep 9, 2017 at 16:58 | history | answered | Igor Rivin | CC BY-SA 3.0 |