How CentralityCalculator Computes Graph Centrality Metrics in Semantica

The CentralityCalculator class in semantica-agi/semantica is a self-contained engine that computes five classic graph centrality measures—degree, betweenness, closeness, eigenvector, and PageRank—using optional NetworkX acceleration with pure-Python fallback implementations.

The Semantica knowledge graph analytics stack relies on CentralityCalculator to quantify node importance across heterogeneous graph structures. Located in semantica/kg/centrality_calculator.py, this class provides a unified interface for calculating centrality metrics while abstracting the complexity of graph normalization and sparse linear algebra operations.

Architecture and Design Layers

The calculator follows a four-layer architecture that separates input handling, algorithm execution, and result formatting.

Initialization and Optional Dependencies

During construction in centrality_calculator.py (lines 106–116), the calculator attempts to import NetworkX to enable optimized C-backed calculations. If NetworkX is unavailable, the class initializes gracefully and relies on internal pure-Python implementations. The constructor also instantiates a progress tracker to provide real-time feedback during long-running computations on large graphs.

Graph Normalization via _graph_view

Before any metric calculation, the calculator converts arbitrary graph representations into a uniform adjacency list. The private method _build_adjacency delegates to build_graph_view in semantica/kg/_graph_view.py (lines 55–66), which handles Neo4j-style dictionaries, custom ContextGraph objects, or raw NetworkX graphs. This normalization ensures isolated nodes are preserved and correctly accounted for in degree and eigenvector calculations.

Metric Computation Strategies

Each centrality algorithm follows a dual-path strategy: prefer NetworkX implementations when available, otherwise execute optimized fallback code.

Degree Centrality Implementation

In calculate_degree_centrality (lines 69–101), the calculator checks for NetworkX and calls nx.degree_centrality if present. Without NetworkX, it iterates the normalized adjacency list to count neighbors for each node, then normalizes scores by dividing by (n‑1) where n is the total node count. This produces a value between 0 and 1 representing the fraction of possible connections a node maintains. Progress tracking calls wrap the counting phase (lines 52–61) to enable UI feedback during computation.

Betweenness Centrality Calculation

The calculate_betweenness_centrality method (lines 68–133) attempts nx.betweenness_centrality first. The fallback implementation executes a BFS from every source node to enumerate all shortest paths, then accumulates middle-node contributions using Brandes' algorithm principles. This O(VE) approach ensures functionality in minimal environments lacking compiled dependencies.

Closeness Centrality Algorithm

For closeness, calculate_closeness_centrality (lines 71–94) similarly prefers NetworkX but defaults to a pure-Python BFS routine. It computes the sum of shortest-path distances from each node to all reachable others, then calculates the ratio of reachable nodes to total distance. Nodes with higher ratios sit closer to the graph's center.

Eigenvector Centrality with Power Iteration

When NetworkX is absent, calculate_eigenvector_centrality (lines 35–66) constructs a symmetric adjacency matrix using NumPy arrays and executes a power iteration loop until the L2 norm change falls below a configurable tolerance. This finds the dominant eigenvector representing recursive importance scores where a node's value depends on the importance of its neighbors. The implementation uses sparse matrices to minimize memory overhead.

PageRank via Sparse Matrix Operations

The calculate_pagerank implementation (lines 22–71) always uses internal sparse-matrix logic rather than NetworkX, keeping the dependency strictly optional. It builds a CSR matrix from filtered neighbors, then iterates:

PR = (1-d)/n + d * A * PR

Where d is the damping factor (default 0.85), A is the transition matrix, and PR is the PageRank vector. The loop converges when changes fall below the tolerance threshold, utilizing scipy.sparse.csr_matrix for memory-efficient computation on large knowledge graphs.

Result Packaging and Aggregation

Every individual method returns a dictionary containing:

• Raw centrality mappings ({node_id: score})
• A pre-sorted list of (node, score) tuples under the key rankings

The orchestrator method calculate_all_centrality (lines 98–118) executes all five metrics sequentially and aggregates outputs into a unified structure under centrality_measures, enabling batch analysis across multiple algorithms.

Practical Usage Example

The following example demonstrates computing all centrality types on a minimal dictionary graph:

from semantica.kg import CentralityCalculator

# Minimal graph representation

graph = {
    "entities": {"A": {}, "B": {}, "C": {}, "D": {}},
    "relationships": [
        ("A", "B"), ("A", "C"), ("B", "C"), ("C", "D")
    ],
}

calc = CentralityCalculator()

# Individual metric calculations

deg = calc.calculate_degree_centrality(graph)
bet = calc.calculate_betweenness_centrality(graph)
close = calc.calculate_closeness_centrality(graph)
eig = calc.calculate_eigenvector_centrality(graph)
pr = calc.calculate_pagerank(graph)

# Batch calculation

all_centralities = calc.calculate_all_centrality(graph)
print("Available measures:", list(all_centralities["centrality_measures"].keys()))

This same interface accepts NetworkX objects directly; the calculator automatically detects and leverages optimized implementations when available.

Summary

• Five metrics supported: degree, betweenness, closeness, eigenvector, and PageRank, each with NetworkX acceleration and pure-Python fallbacks.
• Flexible input handling: The _graph_view.py module normalizes heterogeneous graph formats into consistent adjacency lists, preserving isolated nodes.
• Sparse linear algebra: Eigenvector and PageRank use scipy.sparse.csr_matrix and power iteration for memory-efficient scaling.
• Progress tracking: Built-in tracking calls wrap each metric's major phases for UI integration.
• Unified API: All methods return standardized dictionaries with rankings lists, while calculate_all_centrality aggregates everything into a single structure.

Frequently Asked Questions

How does CentralityCalculator handle missing NetworkX dependencies?

The calculator attempts to import NetworkX during initialization in centrality_calculator.py (lines 106–116). If the import fails, the class operates in pure-Python mode, using BFS-based algorithms for betweenness and closeness, adjacency counting for degree, and NumPy-based power iteration for eigenvector and PageRank calculations.

What graph formats can CentralityCalculator accept?

The class accepts arbitrary graph representations including plain Python dictionaries, custom ContextGraph objects, or NetworkX graphs. The _build_adjacency method delegates to build_graph_view in semantica/kg/_graph_view.py to normalize these inputs into a uniform adjacency list format before computation.

Why does PageRank use a custom implementation instead of NetworkX?

PageRank always uses an internal sparse-matrix power iteration (lines 22–71 of calculate_pagerank) to ensure the metric works even when NetworkX is not installed. This design keeps the dependency optional while utilizing scipy.sparse.csr_matrix for efficient memory usage on large knowledge graphs.

How are centrality results structured and sorted?

Each calculation method returns a dictionary containing raw scores and a rankings key holding a pre-sorted list of (node_id, score) tuples ordered from highest to lowest centrality. The calculate_all_centrality method aggregates all five metrics into a single structure under centrality_measures for convenient batch analysis.

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