Parallel Solution to Betweenness of graph problem (Vyukov)

Betweenness is a metric applied to a vertex within a weighted graph. For the purposes of this problem we will define betweenness of vertex T as the number of shortest paths between two vertices in the graph that includes the vertex T, but does not start or end with vertex T.

The included code and white paper provides a parallel solution for the betweenness computation using a modified version of Dijkstra's algorithm for single source shortest paths was chosen as a baseline single-threaded algorithm for purposes of efficient scalable parallelization. The parallel algorithm uses calls to Dijkstra’s algorithm from each possible source node in the graph, but with an eye to the data dependencies inherent within the problem and the graph. Parallelism is implemented with Intel Threading Building Blocks.

DISCLAIMER: This code is provided by the author as a submitted contest entry, and is intended for educational use only. The code is not guaranteed to solve all instances of the input data sets and may require modifications to work in your own specific environment.

There are downloads available under the Creative Commons License license. Download Now

Include in RSS: 

For more complete information about compiler optimizations, see our Optimization Notice.