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

Matteo Riondato matteo at cs.brown.edu
Mon Jun 22 19:18:47 CEST 2015

Hi All,

I’m one of the authors of the original paper of the algorithm currently implemented in NetworKit as ApproxBetweenness.
First of all, thank you for implementing our work. I gave a look at the implementation.

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?)
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 have some questions about the code organization, which I’d like to understand before I start using and potentially extending NetworKit.

1) I would like to know what was the idea behind using numbers for identifying different approximation algorithms for betweenness centrality: i.e., mine (+Kornaropoulos) algorithm is called ApproxBetweenness and Geisberger et al is called ApproxBetwenness2. These names don’t seem very descriptive to me. May I suggest a plan to rename them to something like ApproxBetweennessRK and ApproxBetweennessGSS? The new names can be added to the current ones which are kept for backward compatibility (maybe with a information message?) for some number of releases, until definitively phased out. I’m asking this because I wonder what would happen if more algorithms are developed and implemented. =)

2) I would like to understand the rationale behind putting the above algorithms in the Centrality module, while the DynApproxBetweenness is in the graph module (at least in the documentation, but not in the code?) Perhaps this is a bug in the documentation?

I’m asking these questions because I’m working on a new algorithm for BC approximation, and I’d like to implement it in NetworKit, and then contribute it back, but I’m not sure where to put it / how to call it, so any suggestion is welcome.

Thank you in advance.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 163 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20150622/f3a4abf5/attachment.sig>

More information about the NetworKit mailing list