[Boost-bugs] [Boost C++ Libraries] #9935: Support edge multiplicity in brandes_betweenness_centrality

Subject: [Boost-bugs] [Boost C++ Libraries] #9935: Support edge multiplicity in brandes_betweenness_centrality
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2014-04-22 09:26:18

#9935: Support edge multiplicity in brandes_betweenness_centrality
---------------------------------------+----------------------------
 Reporter:  Javier Dehesa <javidcf@…>  |      Owner:  jewillco
     Type:  Feature Requests           |     Status:  new
Milestone:  To Be Determined           |  Component:  graph
  Version:  Boost Development Trunk    |   Severity:  Not Applicable
 Keywords:  betweenness                |
---------------------------------------+----------------------------
 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 [http://www.inf.uni-

 konstanz.de/algo/publications/b-vspbc-08.pdf "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.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/9935>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.