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.
This archive was generated by hypermail 2.1.7 : 2017-02-16 18:50:16 UTC