Dynamic Graphs: Betweenness Centrality (BC)

Chapter 6: Betweenness Centrality (BC) in Dynamic Graphs

Introduction

Betweenness Centrality is a metric used to identify the importance of individual nodes in a network. In a dynamic graph, where edges and nodes are added or removed over time, maintaining accurate Betweenness Centrality metrics becomes a non-trivial task. This chapter will explore methods for keeping these measurements up-to-date in dynamic scenarios.

Standard Algorithm for Betweenness Centrality

The standard algorithm for Betweenness Centrality involves calculating shortest paths from each node to all other nodes and then aggregating the frequency at which each node appears on these paths. Here's a quick outline:

  BetweennessCentrality(Graph G):
    1. Initialize all nodes with centrality 0
    2. For each node s in G:
        3. Run a shortest-path algorithm from s to all other nodes
        4. For each shortest path from s to t:
            5. Increment centrality for all nodes on the path by 1/(number of shortest paths from s to t)

Dynamic Graphs and BC

The main challenges for maintaining Betweenness Centrality in dynamic graphs are:

• When a node or edge is added, the shortest paths can change, affecting the centrality scores.
• When a node or edge is removed, likewise, the centrality scores may change.

BC in Dynamic Graphs

Strategies for updating Betweenness Centrality in dynamic graphs include:

1. Recomputing from Scratch: The most straightforward but potentially computationally expensive method.
2. Incremental Updates: More efficient, involving partial recomputation based on the change.

Incremental BC Algorithm

  IncrementalBetweennessCentrality(Graph G_t, BC_Scores):
    1. Detect changes (added/removed vertices and edges)
    2. Partially recompute BC scores affected by the changes
    3. Update BC_Scores accordingly

Conclusion

Betweenness Centrality is a key metric for network analysis, and its maintenance in dynamic graphs requires thoughtful algorithmic approaches. Incremental methods offer a computationally efficient way to keep these measurements accurate in the face of graph changes.