Parallel Solution to Betweenness of graph problem (RuiDiao)

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 computing the Betweenness value of each node through an All-Pairs Shortest Path (APSP) algorithm. Since the APSP problem can be divided into independent Single-Source Shortest Path problems, each thread can solve some SSSP problems from several sources. Parallelism is achieved using Intel Cilk Plus.

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.