Support edge multiplicity in brandes_betweenness_centrality

[Javier Dehesa <javidcf@…>]

There are several possible variations to the Brandes algorithm for the calculation of the betweenness centrality. Several of them were compiled by Brandes himself on his paper ​On variants of shortest-path betweenness centrality and their generic computation.

I need to compute one of these variations, in particular the one which considers edge multiplicities, understood as an edge property representing the frequency or the amount of times a relationship happens. This variation introduces a quite small change in the algorithm, as explained in the section 3.8, algorithm 11 of the referenced paper.

I was thinking of introducing this functionality in the graph library. I roughly know where and what should be added or modified (namely <boost/graph/betweenness_centrality.hpp> and <boost/graph/distributed/betweenness_centrality.hpp>), although I have never made modifications to any Boost library, so I would probably need some advice. Basically, I consider three options:

• Adding a third version of the algorithm, parallel to the Dijkstra and the unweighted version (which would not consider weights).
• Add two versions of the algorithm, one based on the Dijsktra version (considering weights) and another based on the unweighted version.
• Modify both existing implementations of the algorithm, adding an optional map holding the edge multiplicity with a constant value of one by default.

However, I don't know if there is interest in adding this kind of feature to the library, or if it is too specific to be considered useful. Another option would be to expose some interface to be able to inject your own variation of the algorithm from your application, but that would be way more complex to develop, use and document, and probably there would always be uncovered cases.

Just for the record, there is actually a way to make computation with the current implementation, if the edge multiplicities are integers (which is not always true), simply replacing each edge with a number of parallel edges equal to its multiplicity (if the current implementation works for multigraphs, which I think is the case). However, this obviously increases (potentially a lot) the time and space complexity of the already CPU-intensive betweenness calculation.

[Javier Dehesa <javidcf@…>]

While implementing this feature I've realized that the only possible way to introduce a multiplicity parameter without breaking the current API would be as an extra optional parameter in the weighted version of the algorithm - although multiplicities could be considered in weighted or unweighted graphs. The problem is that if we add a new optional parameter to the unweighted signature, it would be impossible to tell if the new parameter is intended to be used as a weight property map or a multiplicity property map. Even breaking the API I can't think of an easy and clean way to work it out.

So I guess that this feature could be implemented only in the weighted version, which by the way is a generalization of the unweighted case, so it's not that bad, you could just use a static_property_map with value 1 as weight.

[Javier Dehesa <javidcf@…>]

Funny enough, after some hours thinking about why my implementation wasn't giving the expected results, I've found out that there was mistake in the referenced algorithm of the referenced paper, as mentioned in the ​publications page of Ulrik Brandes. Seriously though, in 140 publications there are just 2 mistakes, what were the odds?

Anyway, I'll fix that and put a pull request for it.

[Javier Dehesa <javidcf@…>]

I've just put a ​pull request on GitHub for this ticket.