Betweenness Centrality

Betweenness Centrality Class

Betweenness centrality is calculated by finding the nodes with the highest betweenness centrality for each component of the graph. As defined in the project guidelines, this is the node which passes through the most shortest paths in a graph.

This implementation of betweenness centrality is implemented using Brandes algorithm and a Breadth First Search. Firstly, a for loop is written to ensure the algorithm iterates over all components of the graph. A HashMap centrality stores the betweeness Centrality value for each node. A for each loop then uses a Breadth First Search to find the shortest distance to all other nodes, the preceding nodes that pass within all of the shortest paths, and the number of shortest paths from the source node.

Complexity

The Betweenness centrality iterates through each node where at every iteration, it performs a Breadth First Search. It then runs the dependency accumulation algorithm which iterates through a stack taking O(V+E) time. For each node it will take O((V+E)+(V+E)). Therefore the total time complexity is O(V(2V+2E)) which equates to O(V^2+VE).

As mentioned previously, for a sparse graph, the complexity does not change. However, for a dense graph, the complexity simplifies to O(VE).