https://svn.boost.org/trac10/ticket/9935 <p> 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 <a class="ext-link" href="http://www.inf.uni-konstanz.de/algo/publications/b-vspbc-08.pdf"><span class="icon">​</span>On variants of shortest-path betweenness centrality and their generic computation</a>. </p> <p> 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. </p> <p> I was thinking of introducing this functionality in the graph library. I roughly know where and what should be added or modified (namely <code>&lt;boost/graph/betweenness_centrality.hpp&gt;</code> and <code>&lt;boost/graph/distributed/betweenness_centrality.hpp&gt;</code>), although I have never made modifications to any Boost library, so I would probably need some advice. Basically, I consider three options: </p> <ul><li>Adding a third version of the algorithm, parallel to the Dijkstra and the unweighted version (which would not consider weights). </li><li>Add two versions of the algorithm, one based on the Dijsktra version (considering weights) and another based on the unweighted version. </li><li>Modify both existing implementations of the algorithm, adding an optional map holding the edge multiplicity with a constant value of one by default. </li></ul><p> 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. </p> <p> 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. </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/9935 Trac 1.4.3 Javier Dehesa <javidcf@…> Wed, 23 Apr 2014 12:11:45 GMT