Betweenness Centrality Formula

For a node v in a graph G, the betweenness centrality is defined as:

CB(v) = Σ(s≠v≠t) [σ(s,t|v) / σ(s,t)]

Where:

• σ(s,t) is the total number of shortest paths from node s to node t
• σ(s,t|v) is the number of those shortest paths that pass through node v
• The sum is taken over all pairs of nodes s and t where v is neither the source nor target

Normalized Score

Raw betweenness centrality values depend on the size of the network, making them difficult to interpret. We normalize the values to a 0-100 scale:

bridge_score = (CB(v) / max(CB)) × 100

This allows for intuitive comparison: a bridge score of 100 indicates the node with the highest betweenness centrality in the entire network.

Algorithm: Brandes' Algorithm

We use the Brandes algorithm (2001) as implemented in NetworkX. This algorithm efficiently computes betweenness centrality for all nodes in a graph:

import networkx as nx

# Build graph from article links
G = nx.DiGraph()
G.add_edges_from([(source_id, target_id) for each link])

# Compute betweenness centrality
betweenness = nx.betweenness_centrality(G, normalized=False)

Time Complexity: O(n·m) for unweighted graphs, where n is the number of nodes and m is the number of edges. For our Wikipedia dataset with ~1,300 articles, this completes in under a minute.

Approximate Computation (k-sampling)

For very large graphs (>10,000 nodes), exact betweenness centrality computation becomes prohibitively expensive. We offer an approximate method using k-sampling:

# Sample k random nodes instead of all pairs
betweenness_approx = nx.betweenness_centrality(
    G, 
    k=100,           # Sample 100 nodes
    normalized=False
)

This estimates betweenness by computing shortest paths from a random sample of k source nodes rather than all nodes. Accuracy increases with k, but computation time scales linearly with k.

Pipeline Command

Bridge node computation is performed offline as part of the data pipeline:

# Exact computation (recommended for <5K articles)
python -m pipeline bridges

# Approximate computation for large graphs (use k-sampling)
python -m pipeline bridges --sample-k 100

# Disable cluster diversity entropy calculation
python -m pipeline bridges --no-entropy

This command reads the article graph from the database, computes betweenness centrality for all nodes, and updates the articles table with the computed metrics.

Cluster Diversity Entropy

Beyond betweenness centrality, we compute cluster diversity using Shannon entropy to measure how evenly a node's neighbors are distributed across different clusters:

H = -Σ(i) [p(i) × log2(p(i))]

Where:

• p(i) is the proportion of neighbors belonging to cluster i
• Higher entropy indicates more diverse cluster connections
• A node connecting equally to 4 different clusters has higher entropy than one connecting primarily to a single cluster

from collections import Counter
import math

# Count neighbor clusters
neighbor_clusters = [article.cluster_id for article in neighbors]
cluster_counts = Counter(neighbor_clusters)

# Calculate entropy
total = sum(cluster_counts.values())
entropy = -sum(
    (count/total) * math.log2(count/total) 
    for count in cluster_counts.values()
)

Interpretation: High cluster diversity entropy (combined with high betweenness) indicates a truly interdisciplinary bridge connecting multiple knowledge domains. Low entropy suggests the node may be a hub within a single domain rather than a cross-domain bridge.

Betweenness Rank

Nodes are ranked by their betweenness centrality (1 = highest). This provides an ordinal measure that is stable across different graph sizes and computation methods.

GET /api/insights/bridges

Retrieve the top bridge nodes in the knowledge graph.

[
  {
    "article_id": 42,
    "title": "United States",
    "cluster_id": 3,
    "cluster_name": "Geography & Places",
    "betweenness_centrality": 0.00234,
    "bridge_score": 100.0,
    "betweenness_rank": 1,
    "x": 1.23,
    "y": -0.45,
    "z": 2.10,
    "bridge_explanation": "Connects Geography, History, Politics, and Economics",
    "top_neighbor_clusters": [
      {
        "cluster_id": 7,
        "cluster_name": "History & Events",
        "count": 45
      },
      {
        "cluster_id": 12,
        "cluster_name": "Politics & Government",
        "count": 32
      }
    ]
  },
  ...
]

GET /api/insights/bridges/:article_id

Retrieve detailed information about a specific bridge node.

{
  "article_id": 42,
  "title": "United States",
  "summary": "Country in North America...",
  "cluster_id": 3,
  "cluster_name": "Geography & Places",
  "betweenness_centrality": 0.00234,
  "bridge_score": 100.0,
  "betweenness_rank": 1,
  "x": 1.23,
  "y": -0.45,
  "z": 2.10,
  "bridge_explanation": "Connects Geography, History, Politics, and Economics",
  "connected_clusters": [
    {
      "cluster_id": 7,
      "cluster_name": "History & Events",
      "neighbors": [
        {"id": 123, "title": "World War II"},
        {"id": 456, "title": "Cold War"}
      ]
    },
    {
      "cluster_id": 12,
      "cluster_name": "Politics & Government",
      "neighbors": [
        {"id": 789, "title": "Democracy"},
        {"id": 321, "title": "United Nations"}
      ]
    }
  ]
}

Golden Ring Indicator

Bridge nodes are visually distinguished in the 3D globe with a golden ring that orbits the article sphere. This makes them easy to identify while exploring the knowledge graph.

// React Three Fiber implementation
{isBridge && (
  <mesh rotation={[Math.PI / 2, 0, 0]}>
    <ringGeometry args={[0.055, 0.07, 32]} />
    <meshBasicMaterial
      color="#FFD700"
      transparent
      opacity={0.8}
    />
  </mesh>
)}

Bridge Nodes Panel

The right sidebar includes a dedicated Bridge Nodes panel with:

• Toggle: Show/hide bridge node highlighting in the 3D visualization
• Limit Selector: Choose how many top bridges to display (10, 20, 50, or 100)
• Ranked List: Top bridge nodes sorted by bridge score, with click-to-select functionality
• Score Display: Visual bridge score (0-100) for each node

What High Betweenness Centrality Means

Articles with high betweenness centrality typically fall into these categories:

Comparison with Other Centrality Measures