A graph is a mathematical structure that is used to represent interactions or connections among objects. Graphs can be used to mimic a wide range of real-world situations, such as interpersonal ties in a social network, node connections in a computer network, or the movement of items in a supply chain.
Graphs are defined by their vertices and edges. Assessing the significance of vertices and edges in a graph is highly insightful in a number of situations. One of the methods used to quantify this importance of edges and vertices is Betweenness Centrality. The main goal is to identify the number of times the Vertice/Edge is a part of the shortest paths present between Vertices present in the graph.
This is an example computation for a simple graph,
Obviously when scaling graphs to practical situations will lead to computational strain.
The notion of this problem has been clearly established for quite some time and along with it come multiple possible approaches to computing it. One of the more efficient algorithms that solve for Betweenness Centrality is the Brandes algorithm.
As an extension to the conventional implementation of Brandes algorithm for unweighted graphs, I've also implemented a creative way to compute Betweenness Centrality for weighted graphs by extending it with the use of Dijkstra's algorithm. On testing with the code with unweighted and equally weighted methods, they are equivalent.
The documentation of this project can be found here