[Networkit] Betweenness centrality algorithms, small bugs and code organization question

Elisabetta Bergamini elisabetta.bergamini at kit.edu
Wed Jun 24 13:45:09 CEST 2015


Hi Matteo,

thank you again for you remarks.
Here are another couple of comments:

On Jun 22, 2015, at 19:18, Matteo Riondato <matteo at cs.brown.edu> wrote:

> I’d like to point out a minor big in the computation of the sample size: on line 51 of ApproxBetweenness.cpp, the logarithm  inside the floor should be log2, not log. This bug is propagated on line 47 of DynApproxBetweenness.cpp (btw, I assume this is the algorithm from the ALENEX paper, not the one in the upcoming ESA paper, is this latter one implemented and available?)

Yes, this is the algorithm from the ALENEX paper, the one form the ESA paper will be available soon (and thank you for reporting the log2 bug).

> I also have some theoretician rants^Wcomments about the idea of approximating the vertex diameter using samples, especially about calling it an optimization, but they’re minor and I’ll keep them to myself ;)

I agree with you, sampling doesn’t ensure the theoretical guarantee on the maximum approximation error and it’s not an optimization. This has been done at the beginning because the initial implementation of the VD approximation was very slow for graphs with many connected components. The new implementation is much faster so I suggest to simply replace the sampling with the upper bound on VD proposed in Matteo’s paper (and the one we proposed for weighted graphs in our ESA paper).

Best,

Elisabetta




More information about the NetworKit mailing list