How graph_analyzer Calculates Centrality Metrics (Degree, Betweenness, Eigenvector) in Semantica

The graph_analyzer module delegates centrality calculations to the CentralityCalculator class, which implements degree, betweenness, and eigenvector metrics using NetworkX for performance or pure-Python fallbacks for portability.

The graph_analyzer module in the Semantica repository provides high-level graph analytics capabilities for knowledge graph processing. When you need to identify influential nodes through centrality metrics, the GraphAnalyzer class serves as the orchestration layer that routes computation requests to specialized engines. This article examines the implementation across semantica/kg/graph_analyzer.py and semantica/kg/centrality_calculator.py to show exactly how degree, betweenness, and eigenvector centralities are computed.

Entry Point: How GraphAnalyzer Dispatches Centrality Requests

The GraphAnalyzer class acts as a thin wrapper that forwards centrality requests to CentralityCalculator. In semantica/kg/graph_analyzer.py, the method calculate_centrality (lines 68-81) accepts a graph and a centrality_type parameter (defaulting to "degree").

Internally, it delegates to self.centrality_calculator.calculate_all_centrality(), passing the graph and the requested metric type as a list:

self.centrality_calculator.calculate_all_centrality(graph, centrality_types=[centrality_type])

This call (lines 78-80) returns a dictionary containing the raw centrality scores and a sorted ranking of nodes by influence.

Degree Centrality Implementation

The calculate_degree_centrality method in semantica/kg/centrality_calculator.py supports two execution paths depending on whether NetworkX is installed.

NetworkX Fast Path

If NetworkX is available, the calculator converts the internal graph representation to a NetworkX object using _to_networkx, then calls nx.degree_centrality (lines 70-74). This leverages optimized C-backed implementations for maximum performance.

Pure-Python Fallback

Without NetworkX, the calculator builds a lightweight adjacency list via _build_adjacency (which invokes build_adjacency), then counts the degree of each node (lines 21-35). The raw counts are normalized by dividing by (n‑1), where n is the number of nodes, yielding values between 0 and 1.

The method returns a dictionary containing:

• centrality: A mapping of node IDs to normalized scores
• rankings: A sorted list of node IDs by descending score (lines 41-48)

Betweenness Centrality Implementation

The calculate_betweenness_centrality method identifies nodes that act as bridges along the shortest paths between other nodes.

NetworkX Fast Path

When NetworkX is present, the implementation calls nx.betweenness_centrality (lines 85-89) on the converted graph object.

Fallback BFS Implementation

In the pure-Python fallback, the calculator uses _bfs_shortest_paths to collect all shortest paths between every pair of nodes. Each node that lies on a shortest path between a source-target pair receives a count. After iterating over all pairs, raw counts are normalized by the factor (n‑1)(n‑2)/2 (lines 24-31), representing the number of possible node pairs excluding the node itself.

The result structure includes centrality scores and rankings (lines 33-38).

Eigenvector Centrality Implementation

The calculate_eigenvector_centrality method measures node influence based on connections to high-scoring nodes, implemented in semantica/kg/centrality_calculator.py.

NetworkX Fast Path

With NetworkX available, the method invokes nx.eigenvector_centrality (lines 86-89).

Power Iteration Fallback

The fallback implementation constructs an adjacency matrix A and runs a power-iteration scheme until convergence or reaching max_iter (lines 44-53). Upon convergence, the resulting eigenvector is normalized to the range [0, 1].

As with other metrics, the method returns a centrality dictionary and a sorted rankings list (lines 66-73).

Usage Examples

Here is how to calculate each centrality metric using GraphAnalyzer:

from semantica.kg.graph_analyzer import GraphAnalyzer

# Load or construct a KG in the expected dict format

graph = {
    "entities": [...],
    "relationships": [...]
}

analyzer = GraphAnalyzer()

# 1. Degree centrality (default)

deg = analyzer.calculate_centrality(graph, centrality_type="degree")
print("Top degree node:", deg["rankings"][0])

# 2. Betweenness centrality

bet = analyzer.calculate_centrality(graph, centrality_type="betweenness")
print("Node with highest betweenness:", bet["rankings"][0])

# 3. Eigenvector centrality

eig = analyzer.calculate_centrality(graph, centrality_type="eigenvector")
print("Most influential node (eigenvector):", eig["rankings"][0])

All three calls ultimately invoke CentralityCalculator.calculate_all_centrality, which runs the appropriate algorithm and returns a unified result dictionary with both raw scores and rankings.

Summary

• The graph_analyzer module delegates all centrality calculations to CentralityCalculator, keeping the high-level API thin and maintainable.
• Degree centrality counts connections and normalizes by (n‑1), using NetworkX when available or adjacency lists otherwise.
• Betweenness centrality counts shortest-path memberships and normalizes by (n‑1)(n‑2)/2, using BFS traversal in the fallback implementation.
• Eigenvector centrality uses power iteration on the adjacency matrix when NetworkX is unavailable, converging on the principal eigenvector.
• All methods return standardized output containing centrality scores and rankings lists.

Frequently Asked Questions

What centrality types does GraphAnalyzer support?

According to the source code in semantica/kg/centrality_calculator.py (lines 95-102), the calculator supports degree, betweenness, closeness, eigenvector, and pagerank. The GraphAnalyzer.calculate_centrality method accepts any of these types as the centrality_type parameter.

How does the NetworkX fallback work?

If NetworkX is not installed, CentralityCalculator automatically switches to pure-Python implementations. For degree centrality, it builds an adjacency list; for betweenness, it performs BFS to find shortest paths; for eigenvector, it uses matrix power iteration. These fallbacks ensure the analytics work without external dependencies, though performance is slower on large graphs.

What is the normalization factor for betweenness centrality?

The betweenness centrality normalization factor is (n‑1)(n‑2)/2, where n is the number of nodes in the graph. This represents the total number of possible shortest paths that could pass through a given node, ensuring the final score falls between 0 and 1.

Can I calculate multiple centrality metrics at once?

Yes. While GraphAnalyzer.calculate_centrality computes one metric at a time, you can call centrality_calculator.calculate_all_centrality() directly with multiple types in the centrality_types list (e.g., ["degree", "betweenness"]). This method merges results into a single dictionary, avoiding redundant graph conversions.

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