# How Semantica Computes Betweenness Centrality: NetworkX vs. Pure-Python Implementation

> Semantica computes betweenness centrality using NetworkX or a pure-Python BFS. Discover how Semantica optimizes network analysis for flexibility and performance in your projects.

- Repository: [Semantica /semantica](https://github.com/semantica-agi/semantica)
- Tags: deep-dive
- Published: 2026-09-10

---

**Semantica computes betweenness centrality through a dual-strategy approach in the `CentralityCalculator` class, preferring NetworkX's optimized algorithms when available while providing a handcrafted BFS fallback for dependency-free environments.**

Semantica implements betweenness centrality calculation in [`semantica/kg/centrality_calculator.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/kg/centrality_calculator.py) to quantify how often nodes act as bridges along shortest paths in knowledge graphs. The library automatically selects the fastest available method to compute betweenness centrality scores, ensuring high performance in data-science workflows while maintaining portability in constrained deployments.

## The CentralityCalculator Architecture

The computation logic resides in the **`CentralityCalculator`** class located at [`semantica/kg/centrality_calculator.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/kg/centrality_calculator.py). This class serves as the primary interface for all graph centrality operations within the Semantica ecosystem, abstracting away the complexity of algorithm selection and graph format conversion.

### Primary Method: calculate_betweenness_centrality

The method `calculate_betweenness_centrality` accepts a graph input—either a dictionary containing `"entities"` and `"relationships"` or a pre-built graph object—and returns a standardized result dictionary. When invoked, the calculator evaluates the execution environment and branches into one of two implementation paths.

## Dual-Mode Computation Strategy

Semantica employs a hierarchical execution model that prioritizes computational efficiency through optional dependencies while guaranteeing functionality via pure-Python implementations.

### NetworkX Optimization Path

If **NetworkX** is installed and accessible, the calculator executes the optimized path:

1. The private helper **`_to_networkx`** converts the internal graph representation to a NetworkX graph object using `build_graph_view` from [`semantica/utils/_graph_view.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/utils/_graph_view.py).
2. The calculator invokes NetworkX’s native `betweenness_centrality` function, which uses highly optimized C-backed algorithms for large-scale graph traversal.
3. The function returns a dictionary mapping node identifiers to centrality scores, which the calculator sorts into a descending ranking list.

This path delivers superior performance for large knowledge graphs with complex topologies.

### Pure-Python BFS Fallback

When NetworkX is unavailable, disabled via configuration, or the import fails, the calculator seamlessly falls back to a handcrafted algorithm:

1. **`_build_adjacency`** constructs an adjacency list representation from the input graph structure.
2. For **every source node**, the private method **`_bfs_shortest_paths`** performs a breadth-first search to enumerate all shortest paths to each reachable target node.
3. Each discovered shortest path contributes **+1** to the betweenness count of every intermediate node along that path, explicitly excluding the source and target endpoints.
4. After processing all source-target pairs, raw counts are **normalized** by dividing by the factor \((n-1)(n-2)/2\), where \(n\) represents the total number of nodes. This yields the classic betweenness centrality values ranging between 0 and 1.
5. The normalized scores are sorted into a ranked list from highest to lowest.

## Result Structure and Return Format

Regardless of the computation path taken, `calculate_betweenness_centrality` returns a dictionary with two consistent keys:

- **`"centrality"`**: A mapping of node identifiers to their computed betweenness scores (floating-point values).
- **`"rankings"`**: A list of objects formatted as `{ "node": <id>, "score": <value> }`, ordered descending by score to facilitate immediate identification of the most critical bridge nodes.

## Implementation Examples

### Basic Usage with Default Configuration

The following example demonstrates standard invocation with automatic algorithm selection:

```python
from semantica.kg import CentralityCalculator

# graph can be a dict with "entities"/"relationships" or a NetworkX graph

calculator = CentralityCalculator()
betweenness = calculator.calculate_betweenness_centrality(graph)

print(betweenness["centrality"])   # node → score mapping

print(betweenness["rankings"][0])  # top-ranked node object

```

### Forcing the Fallback Implementation

To bypass NetworkX even when installed—useful for testing deterministic behavior or avoiding heavy dependencies—explicitly disable the optimization:

```python
from semantica.kg import CentralityCalculator

calc = CentralityCalculator()
calc.use_networkx = False          # bypass NetworkX optimization

result = calc.calculate_betweenness_centrality(graph)

# result maintains identical structure to NetworkX-based output

```

### Pipeline Integration

Integrate centrality calculation into data processing pipelines to enrich graph metadata for visualization or downstream analysis:

```python
from semantica.kg import CentralityCalculator

def enrich_graph_with_centrality(graph):
    centrality = CentralityCalculator().calculate_betweenness_centrality(graph)
    # Attach centrality scores to node metadata

    for node, score in centrality["centrality"].items():
        graph.nodes[node]["betweenness"] = score
    return graph

```

## Key Source Files

The betweenness centrality implementation spans several critical files within the Semantica repository:

- **[`semantica/kg/centrality_calculator.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/kg/centrality_calculator.py)**: Core implementation containing the `CentralityCalculator` class and both algorithmic paths.
- **[`semantica/kg/graph_analyzer.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/kg/graph_analyzer.py)**: Higher-level wrapper that instantiates `CentralityCalculator` and exposes centrality methods to the broader system.
- **[`semantica_mcp/mcp/tools/graph.py`](https://github.com/semantica-agi/semantica/blob/main/semantica_mcp/mcp/tools/graph.py)**: Demonstrates production usage of betweenness calculations within the MCP (multi-component) toolset.
- **[`semantica/export/distance_exporter.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/export/distance_exporter.py)**: Illustrates consumption of betweenness scores during distance-band metric exports.
- **[`semantica/utils/_graph_view.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/utils/_graph_view.py)**: Supplies `build_graph_view` utilities for converting internal graph formats to NetworkX objects.

## Summary

- **Semantica** computes betweenness centrality through the `CentralityCalculator` class in [`semantica/kg/centrality_calculator.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/kg/centrality_calculator.py).
- The system prioritizes **NetworkX**'s optimized implementation via the `_to_networkx` conversion helper when available.
- A **pure-Python BFS fallback** processes all shortest paths using `_bfs_shortest_paths` and normalizes results by \((n-1)(n-2)/2\) when NetworkX is absent.
- Results follow a standardized format containing both a `"centrality"` score map and a sorted `"rankings"` list.
- Developers can force the fallback algorithm by setting `use_networkx = False` on the calculator instance.

## Frequently Asked Questions

### What class handles betweenness centrality in Semantica?

The **`CentralityCalculator`** class in [`semantica/kg/centrality_calculator.py`](https://github.com/semantica-agi/semantica/blob/main/semantica/kg/centrality_calculator.py) encapsulates all betweenness centrality logic. This class provides the `calculate_betweenness_centrality` method as the primary public interface for computing bridge-node importance in knowledge graphs.

### Does Semantica require NetworkX to compute betweenness centrality?

No, NetworkX is an **optional dependency**. Semantica gracefully degrades to a pure-Python implementation using breadth-first search if NetworkX is not installed. However, installing NetworkX significantly improves performance for large graphs through optimized C-based algorithms.

### How does Semantica normalize betweenness centrality scores?

When using the fallback implementation, Semantica normalizes raw path counts by dividing by \((n-1)(n-2)/2\), where \(n\) is the number of nodes. This denominator represents the maximum possible number of node pairs (excluding the node itself), yielding standardized centrality values between 0 and 1.

### Can I force Semantica to use the pure-Python implementation?

Yes, set the **`use_networkx`** attribute to `False` on your `CentralityCalculator` instance before calling `calculate_betweenness_centrality`. This bypasses the NetworkX optimization even when the library is installed, ensuring deterministic execution of the handcrafted BFS algorithm.