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

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 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. 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.
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:

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:

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:

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: Core implementation containing the CentralityCalculator class and both algorithmic paths.
• 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: Demonstrates production usage of betweenness calculations within the MCP (multi-component) toolset.
• semantica/export/distance_exporter.py: Illustrates consumption of betweenness scores during distance-band metric exports.
• 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.
• 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 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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}