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

Matteo Riondato matteo at cs.brown.edu
Tue Jun 23 15:13:07 CEST 2015

> On Jun 22, 2015, at 5:28 PM, Christian Staudt <christian.staudt at kit.edu> wrote:
> On 22 Jun 2015, at 19:18, Matteo Riondato <matteo at cs.brown.edu> wrote:
>> I’m asking this because I wonder what would happen if more algorithms are developed and implemented. =)
> 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.

It is easy to extend RK to give a multiplicative error guarantees for all nodes whose centrality is above a user-specified threshold. Obviously you’ll have to sample more, and now you have an additional parameter to fix, without previous knowledge about it…a possibility could be to run absolute-error RK first, to understand the parameter, and then run the relative-error RK, like we do in the relative-error top-k variant of RK.

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

Yes, this is a reasonable comment. Stay tuned ;)

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

In the documentation for the C++ modules (https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/cpp_doc.html) .
The DynApproxBetweenness class is listed under the graph module (https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/doxyhtml/group__graph.html)
while the ApproxBetweenness* and the Betweenness classes are in the centrality module (https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/doxyhtml/group__centrality.html)

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

Thanks. I may contact you in the future =)

-------------- 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/20150623/f1599341/attachment.sig>

More information about the NetworKit mailing list