Community Detection Algorithms in Graphs: From Theory to Production Knowledge Graphs

Why Community Detection Matters

Community detection is the process of partitioning a graph into groups of densely connected nodes — communities — where intra-group connections are significantly more numerous than inter-group connections. It is one of the most practically useful families of graph algorithms, yet it rarely gets the dedicated treatment it deserves outside academic literature.

In production knowledge graphs, community detection serves three critical roles:

• GraphRAG indexing: Microsoft's GraphRAG pipeline uses the Leiden algorithm to partition entity graphs into communities, then summarises each community independently. Without community detection, global graph summarisation is computationally intractable.
• Fraud detection: Financial crime investigators use community detection to uncover tightly-knit rings of accounts that transact primarily among themselves — a strong signal for money laundering or synthetic identity fraud.
• Recommendation systems: Content platforms cluster users by interaction patterns, then recommend items popularised within a user's community before expanding to broader discovery.

This article walks through the four most important community detection algorithms — Louvain, Leiden, Label Propagation, and K-Clique — with working code examples, complexity analysis, and deployment guidance.

Algorithm Taxonomy

Community detection algorithms fall into two broad families:

Family	Approach	Examples	Scalability
Agglomerative (bottom-up)	Merge nodes into communities by optimising a quality function	Louvain, Leiden	O(n log n) — suitable for millions of nodes
Divisive (top-down)	Remove edges with highest betweenness to isolate communities	Girvan-Newman	O(n³) — impractical beyond thousands of nodes
Label propagation	Propagate community labels through neighbours until consensus	LPA	Near-linear — the fastest option
Clique-based	Find maximal cliques, then merge overlapping cliques into communities	K-Clique Percolation	NP-hard in worst case — use on small subgraphs

For production knowledge graphs, the agglomerative family (Louvain, Leiden) dominates because it scales to millions of nodes and produces deterministic, hierarchical results.

Louvain Algorithm

The Louvain algorithm, published by Blondel et al. in 2008, remains the most widely deployed community detection method. It optimises modularity — a quality score that compares the density of edges inside communities against a randomised null model.

How It Works

Louvain operates in two phases that repeat iteratively:

1. Local optimisation: For each node, evaluate the modularity gain of moving it to a neighbouring community. Perform the move that yields the largest positive gain. Repeat until no move improves modularity.
2. Aggregation: Contract each community into a single "super-node," weighting edges between super-nodes by the sum of inter-community edges. Repeat phase 1 on the aggregated graph.

The algorithm terminates when modularity stops increasing between iterations.

Python with NetworkX

import networkx as nx
import matplotlib.pyplot as plt

G = nx.karate_club_graph()

# Louvain via the community package
from networkx.algorithms.community import louvain_communities

communities = louvain_communities(G, seed=42)
community_map = {}
for idx, community in enumerate(communities):
    for node in community:
        community_map[node] = idx

# Visualise the result
pos = nx.spring_layout(G, seed=42)
nx.draw_networkx_nodes(
    G, pos,
    node_color=[community_map[n] for n in G.nodes()],
    cmap=plt.cm.Set2,
    node_size=300
)
nx.draw_networkx_edges(G, pos, alpha=0.3)
plt.title("Karate Club — Louvain Communities")
plt.show()

The Zachary Karate Club graph (34 nodes, 78 edges) cleanly partitions into two communities that correspond almost exactly to the real-world split that occurred in the original 1977 study — a classic demonstration of Louvain's effectiveness on small graphs.

Complexity

Louvain runs in O(n log n) on sparse graphs, where n is the number of nodes. Each pass through the local optimisation phase is O(m) for m edges, and the number of passes is typically < 10 for graphs with realistic community structure. This makes it suitable for graphs with tens of millions of nodes.

Known Limitation: Resolution Limit

Louvain has a well-documented weakness: it may fail to detect small communities in large graphs because the modularity objective has a resolution limit — it favours large communities over small ones. This is where Leiden improves upon Louvain.

Leiden Algorithm

Leiden, published by Traag et al. in 2019, is a strict improvement over Louvain. It introduces a refinement phase between Louvain's local optimisation and aggregation steps, which guarantees that communities are well-connected (every partition is subset of a connected subgraph) and addresses the resolution limit.

Why Leiden Replaced Louvain

Property	Louvain	Leiden
Guarantees connected communities	✗	✓
Resolution-limit proof	✗	✓
Speed on large graphs	Fast	Faster (refinement phase converges faster than Louvain's aggregation)
Deterministic with seed	Approximate	Approximate

In practice, Leiden is now the recommended default for community detection. Neo4j's Graph Data Science (GDS) library uses Leiden as its primary community detection algorithm, and Microsoft's GraphRAG implementation relies on Leiden for its hierarchical community structure.

Neo4j GDS — Leiden with Cypher

-- Create a named graph projection
CALL gds.graph.project(
  'myGraph',
  'Entity',
  {RELATED_TO: {orientation: 'UNDIRECTED'}}
);

-- Run Leiden community detection
CALL gds.leiden.write('myGraph', {
  writeProperty: 'communityId',
  includeIntermediateCommunities: true,
  maxLevels: 10
})
YIELD communityCount, modularity, modularities, ranLevels;

-- Query the resulting communities
MATCH (e:Entity)
RETURN e.communityId AS community, count(*) AS memberCount
ORDER BY memberCount DESC
LIMIT 20;

The includeIntermediateCommunities: true option returns the hierarchical community structure — each level in the hierarchy corresponds to a coarser partitioning. This is what GraphRAG uses: level 0 contains fine-grained communities for local retrieval, higher levels contain broader summaries for global understanding.

Label Propagation Algorithm (LPA)

LPA is the simplest community detection method. Every node starts with a unique label. In each iteration, every node adopts the label that appears most frequently among its neighbours (ties are broken randomly). After enough iterations, densely connected regions converge to a consensus label.

from networkx.algorithms.community import label_propagation_communities

G = nx.karate_club_graph()
communities = list(label_propagation_communities(G))

for i, comm in enumerate(communities):
    print(f"Community {i}: {sorted(comm)}")

Strengths and Weaknesses

• Speed: Near-linear time — O(m) per iteration, typically converging in 5–10 iterations. It is the fastest community detection algorithm available and can scale to billions of edges on a single machine.
• Non-determinism: Because tie-breaking is random, LPA produces different results across runs. This makes it unsuitable for audit-trail applications where reproducibility matters.
• Quality: LPA tends to produce a single giant community plus many tiny ones on graphs with heterogeneous degree distributions. It works best on graphs with uniform density.

Use LPA when: You need a quick, approximate partitioning of an extremely large graph and reproducibility is not a requirement — for example, pre-filtering a billion-edge social graph before applying a more expensive algorithm.

K-Clique Percolation

K-Clique percolation takes a different approach: instead of optimising a global quality function, it finds communities by identifying overlapping cliques. A k-clique community is the union of all k-cliques (complete subgraphs of k nodes) that can be reached through adjacent k-cliques sharing k-1 nodes.

import networkx as nx
from networkx.algorithms.community import k_clique_communities

G = nx.karate_club_graph()
communities = list(k_clique_communities(G, k=3))

for i, comm in enumerate(communities):
    print(f"K=3 Community {i}: {sorted(comm)}")

Why K-Clique Matters

Most community detection algorithms (Louvain, Leiden, LPA) assign each node to exactly one community — they produce a partition. But real-world graphs have overlapping community structure: a person belongs to their family, their workplace, and their hobby group simultaneously. K-Clique percolation is one of the few algorithms that naturally produces overlapping communities.

The trade-off is computational cost: finding all k-cliques is NP-hard in the worst case. In practice, k=3 or k=4 on graphs with fewer than 100k nodes is feasible. For larger graphs, use K-Clique as a refinement step on individual Louvain/Leiden communities rather than on the full graph.

Choosing the Right Algorithm

The decision depends on graph size, required determinism, and whether overlapping communities are needed:

Criterion	Leiden	Louvain	LPA	K-Clique
Graph size	≤10⁸ nodes	≤10⁸ nodes	≤10⁹ nodes	≤10⁵ nodes
Deterministic	Approx.	Approx.	✗	✓ (with fixed k)
Overlapping communities	✗ (partition)	✗ (partition)	✗ (partition)	✓
Hierarchical output	✓	✓ (limited)	✗	✗
Production readiness	★★★★★	★★★★☆	★★★☆☆	★★☆☆☆
Implementation availability	Neo4j GDS, NetworkX, igraph	NetworkX, igraph, scikit-network	NetworkX, Neo4j GDS	NetworkX

Community Detection in Production Knowledge Graphs

GraphRAG Pipeline Integration

The most prominent production use of community detection in 2026 is within GraphRAG indexing pipelines. The standard flow:

1. Entity extraction: Extract entities and relationships from documents into a knowledge graph.
2. Graph construction: Build a weighted, undirected graph from entity co-occurrence or relationship density.
3. Community detection: Run Leiden (or Louvain for smaller graphs) to partition the entity graph into communities.
4. Community summarisation: Generate a natural-language summary for each community using an LLM.
5. Two-tier retrieval: At query time, search community summaries (global) first, then drill into entity details (local) within the most relevant community.

# Minimal GraphRAG-style community detection pipeline
from neo4j import GraphDatabase
import networkx as nx

driver = GraphDatabase.driver("neo4j://localhost:7687", auth=("neo4j", "password"))

# Fetch entity co-occurrence graph
with driver.session() as session:
    rows = session.run("""
        MATCH (e1:Entity)-[r:CO_OCCURS]-(e2:Entity)
        RETURN e1.id AS source, e2.id AS target, r.weight AS weight
    """)
    G = nx.Graph()
    for row in rows:
        G.add_edge(row["source"], row["target"], weight=row["weight"])

# Run Leiden community detection
from networkx.algorithms.community import louvain_communities

communities = louvain_communities(G, weight="weight", seed=42)

# Write community assignments back to Neo4j
with driver.session() as session:
    for idx, community in enumerate(communities):
        for node_id in community:
            session.run(
                "MATCH (e:Entity {id: $id}) SET e.communityId = $cid",
                id=node_id, cid=idx
            )

Monitoring and Validation

Community detection results should never be trusted blindly. Validate with these metrics:

• Modularity score: A modularity > 0.3 generally indicates meaningful community structure. Values > 0.7 suggest very strong partitioning.
• Community size distribution: A healthy distribution has a few large communities and many small ones — power-law-like. A single community containing 95% of nodes suggests the resolution limit is at play (try Leiden with a higher resolution parameter).
• Stability analysis: Run the algorithm multiple times with different random seeds. If community assignments vary dramatically, the graph may lack genuine community structure, or the resolution parameter needs adjustment.

Conclusion

Community detection is the bridge between raw graph structure and actionable insight. Leiden has become the production standard for good reason — it combines scalability with theoretical guarantees that Louvain cannot match. Label Propagation remains the fastest option for billion-edge graphs where approximate results suffice, and K-Clique percolation fills the niche for overlapping community analysis on smaller subgraphs.

As GraphRAG continues to drive adoption of knowledge graphs in AI pipelines, understanding these algorithms — their trade-offs, implementations, and failure modes — is no longer optional for engineers building graph-backed systems.