Q: Compute complete Betweenness Centrality

[delanyinspiron6400]

TL:DR: What is the difference between the three variants of BC and how can one compute the complete BC for a graph (like in Hybrid_BC)?

I have a few questions regarding computing the BC of a graph. It seems there are three variants in the repository:

• BCCentrality
• ExactBC
• ApproximateBC What is the difference between these three variants, a few of them are out-commented in the BCTest.cu, hence I'm not completely sure if they are working as of now?

Furthermore, as far as I can see, these algorithms seem to require a root node to be passed, does this mean that I'd have to sequentially call the algorithms for all nodes in a graph to actually compute the BC? I guess internally, some form of Brandes is done, hence does this mean that by passing a root node, only a partial BC result is computed, looking at all paths from this given root node? Could I then simply do something like this:

BCCentrality bc(hornet_graph);
for(auto i = 0; i < graph.nV(), ++i)
{
  bc.setRoot(i);
  bc.run();
}

or is there a canonical approach to compute the BC for a graph I'm missing?

Thanks very much! 😄

[delanyinspiron6400]

And unrelated to this question something else, I was redirected to this repository with my question, as the original Hornet is seemingly not maintained anymore, but it seems the current state of the repository does not build. In the original, I had to fix small stuff in xlib (some includes missing so it works with gcc on ArchLinux), but in this repository, it seems more is missing. Looking at the repository structure, there was a module rmm, which was removed, but which is referenced throughout the code, even manually pulling it into externals/rmm did not resolve this issue.

Should this repository be useable at the moment as a public repository? Or should I stick with the original?

[ogreen]

I will start off with the 2nd comment\question by saying that the "getting started" documentation for this repo needs to be updated. To build this repo, please visit: https://rapids.ai/start.html. You will need to use conda packages to get rmm working.

The three so called variants of BC are actually two variants: exact and approximate. There is one class BCCentrality that does the actual traversal according to Brandes algorithm. Exact BC does the traversal for each root\vertex in the graph. Approximate BC does the traversal for a subset of vertices. How the subset of vertices is selected is "open" to debate. Two popular approaches are: 1) Pre-select the roots (using some random distribution). 2) Choose one root at a time and after each traversal, choose the next root based on the BC values.

[delanyinspiron6400]

Thank you very much, I got it to run with this description. :smile: