Centrality and Community Detection Algorithms in Semantica: Complete Implementation Guide

Semantica implements five centrality algorithms (degree, betweenness, closeness, eigenvector, and PageRank) and two community detection algorithms (label propagation and Louvain) through the CentralityCalculator and CommunityDetector classes.

The semantica-agi/semantica repository provides a comprehensive graph-analytics toolkit for analyzing Knowledge Graphs (KGs). This guide examines the specific algorithms available for centrality calculations and community detection, their implementation details, and practical usage patterns.

Centrality Calculation Algorithms

All centrality methods in Semantica are implemented in semantica/kg/centrality_calculator.py through the CentralityCalculator class. The class provides both individual algorithmic methods and a batch execution interface.

Degree Centrality

Degree centrality counts direct connections of a node and normalizes by the maximum possible degree. This is the fastest centrality measure and works even without NetworkX installed.

from semantica.kg import CentralityCalculator

calc = CentralityCalculator()
deg = calc.calculate_degree_centrality(my_graph)
print("Top 5 nodes by degree:", deg["rankings"][:5])

Source: centrality_calculator.py (lines 29‑31)

Betweenness Centrality

Betweenness centrality measures how often a node lies on shortest paths between other nodes, identifying bridge nodes that connect otherwise separate parts of the graph.

btw = calc.calculate_betweenness_centrality(my_graph)

Source: centrality_calculator.py (lines 68‑72)

Closeness Centrality

Closeness centrality evaluates the average distance from a node to all other reachable nodes, highlighting nodes that can quickly reach others in the network.

close = calc.calculate_closeness_centrality(my_graph)

Source: centrality_calculator.py (lines 37‑40)

Eigenvector Centrality

Eigenvector centrality assigns higher scores to nodes connected to other high-scoring nodes, capturing the principle that connections to influential nodes matter more than connections to peripheral ones.

eigen = calc.calculate_eigenvector_centrality(my_graph)

Source: centrality_calculator.py (lines 97‑101)

PageRank

PageRank implements Google's random-walk based ranking algorithm. It supports filtering by node labels or relationship types and accepts a custom damping factor.

# PageRank with custom damping factor

pr = calc.calculate_pagerank(my_graph, damping_factor=0.9)
print("Node with highest PageRank:", max(pr["centrality"], key=pr["centrality"].get))

Source: centrality_calculator.py (lines 82‑86)

Batch Centrality Execution

The calculate_all_centrality method runs selected subsets or all centrality measures simultaneously, returning a unified result structure:

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

Community Detection Algorithms

Community detection is handled by semantica.kg.community_detector.CommunityDetector in semantica/kg/community_detector.py. Both algorithms expose the same detect_communities(graph, method=...) interface.

Label Propagation

Label propagation is a fast, iterative algorithm that spreads label information across the graph to form communities. It requires no prior knowledge of the number of communities and scales well to large graphs.

from semantica.kg import CommunityDetector

comm_det = CommunityDetector()
communities = comm_det.detect_communities(my_graph, method="label_propagation")
print("Number of communities found:", len(communities["communities"]))

The algorithm is registered in semantica/kg/registry.py and verified in tests/kg/test_registry.py (lines 36‑45).

Louvain Algorithm

Louvain is a modularity-optimization method for hierarchical community detection. In Semantica, it is also available through the strategy="community" chunker for graph partitioning tasks.

lou = comm_det.detect_communities(my_graph, method="louvain")
print("Community sizes:", [len(c) for c in lou["communities"]])

The Louvain option appears in chunking tests at tests/split/test_chunkers.py (lines 387‑389).

Algorithm Registry and Extensibility

Semantica maintains a centralized registry of available KG algorithms in semantica/kg/registry.py. This registry catalogs both centrality and community detection methods, enabling:

• Runtime discovery of available algorithms
• Consistent parameter validation
• CLI integration (semantica kg analyze --mode centrality / --mode community)

The registry is validated through test coverage in tests/kg/test_registry.py, ensuring all documented algorithms remain accessible.

Real-World Usage Patterns

The test suite at tests/kg/test_real_world_scenarios.py demonstrates practical applications combining both centrality and community detection workflows. Typical patterns include:

1. Node importance ranking — run PageRank or eigenvector centrality to identify key entities
2. Structural analysis — use betweenness centrality to find bottleneck nodes
3. Community-aware processing — detect communities with label propagation, then analyze each community's internal centrality distribution

Summary

• Five centrality algorithms: degree, betweenness, closeness, eigenvector, and PageRank — all implemented in semantica/kg/centrality_calculator.py
• Two community detection algorithms: label propagation and Louvain — exposed through semantica/kg/community_detector.py
• Unified interfaces: CentralityCalculator and CommunityDetector classes provide consistent APIs with batch execution options
• Registry-backed extensibility: semantica/kg/registry.py maintains the algorithm catalog for runtime discovery and CLI integration
• Performance considerations: degree centrality requires no external dependencies; other algorithms leverage NetworkX when available

Frequently Asked Questions

What is the fastest centrality algorithm in Semantica?

Degree centrality is the fastest option because it only counts direct neighbors without requiring shortest-path calculations or iterative convergence. According to the source code, it also works without NetworkX installed, making it the most portable choice for basic node importance ranking.

Can I run all centrality measures at once?

Yes, use calculate_all_centrality. This method executes all supported centrality algorithms in a single call and returns a unified dictionary with results under the "centrality_measures" key, eliminating the need for multiple individual method invocations.

Which community detection algorithm should I choose for large graphs?

Label propagation is recommended for large graphs due to its near-linear time complexity and minimal memory overhead. Louvain provides higher-quality communities through modularity optimization but may be slower on very large networks. Both are available via the same detect_communities interface.

Does Semantica require NetworkX for graph analytics?

Partially. Degree centrality works without NetworkX. Betweenness, closeness, eigenvector centrality, PageRank, and both community detection algorithms require NetworkX as the underlying computation engine. The CentralityCalculator handles graceful degradation where possible.

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