Implement Betweenness Centrality Algorithm

[pankaj-bind]

Description:

Betweenness Centrality is a graph centrality measure that quantifies the importance of a node based on how often it lies on the shortest paths between other nodes in the graph[1]. It measures the extent to which a vertex lies on paths between other vertices, making it crucial for identifying nodes that serve as bridges or bottlenecks in network communication.

Why is this needed?

This algorithm is widely used in network analysis problems, such as:

• Social network analysis - Identifying influential individuals who connect different groups
• Transportation networks - Finding critical intersections or stations
• Communication networks - Detecting key routers or switches that handle the most traffic
• Biological networks - Identifying important proteins in metabolic pathways
• Web analysis - Finding important web pages that connect different communities

Tasks:

• Implement the Betweenness Centrality algorithm class using shortest path computation for all node pairs
• Ensure the function accepts both directed and undirected graphs
• Return centrality scores for all nodes in the network (normalized between 0 and 1)
• Optimize implementation using efficient shortest path algorithms (BFS for unweighted, Dijkstra for weighted)
• Write comprehensive unit tests to verify correctness with known graph examples
• Add support for both vertex betweenness and edge betweenness centrality
• Include proper documentation with complexity analysis (O(VE) for unweighted, O(VE + V²log V) for weighted graphs)