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

Christian Staudt christian.staudt at kit.edu
Mon Jun 22 23:28:16 CEST 2015

Hi Matteo,
thanks for your feedback, which is very valuable. Let me answer some of your questions, while others I pass on to betweenness expert Elisabetta.

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

> 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?

I agree. There’s no particular rationale behind these names, it’s just that one was implemented first. I’m fine with your suggested names. In general I suggest to name algorithms in NetworKit by what they do (user’s point of view), not who invented them (academic’s point of view), but things like ApproxBetweennessWithBoundedError and ApproxBetweennessWhereAnythingGoes seem a bit ugly...

>  I’m asking this because I wonder what would happen if more algorithms are developed and implemented. =)

A general remark on “redundant” implementations in NetworKit: I consider selection and recommendation of algorithms as an important aspect of the package. Therefore I’m not in favor of continuing to release an algorithm if we have a clearly better alternative. If one algorithm is not clearly better than another, users should have a choice of both - which is the case with RK and GSS.

Nonetheless, we need to decide on the default algorithm for scalable betweenness, and this is still open: RK provides a bound on the error, while GSS doesn't. Then again, some have questioned the usefulness of an additive error bound on betweenness centrality, which is a fraction. Furthermore, Sanders has made a strong point: RK considers just a single s-t-path per sample, thereby throwing away much information it has previously computed, which could be used to estimate betweenness. GSS uses all the shortest paths it computes.

> 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?

DynApproxBetweenness is in the centrality module as far as the code is concerned. Probably a documentation bug - where exactly did you find it?

> 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.

You are very welcome to contribute, and feel free to let us know anytime we can help. Your algorithm belongs in the centrality module and should inherit from the Centrality base class.


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

More information about the NetworKit mailing list