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.

Python Leiden with igraph

For Python-based pipelines outside Neo4j, the igraph library provides a fast, well-tested Leiden implementation. Unlike the NetworkX Louvain example earlier, igraph runs Leiden natively in C with Python bindings, making it suitable for graphs with millions of nodes on a single machine:

import igraph as ig

# Load the Zachary Karate Club graph
G = ig.Graph.Famous("Zachary")

# Run Leiden community detection
partition = G.community_leiden(
    objective_function="modularity",
    weights=None,
    resolution=1.0,
    beta=0.01
)

print(f"Number of communities: {len(partition)}")
print(f"Modularity: {partition.modularity:.4f}")
for idx, community in enumerate(partition):
    print(f"Community {idx}: {sorted(community)}")

The resolution parameter controls community granularity — values below 1.0 produce fewer, larger communities; values above 1.0 produce more, smaller ones. The beta parameter governs randomness in the refinement phase; the default of 0.01 works well for most graphs. In benchmarks on a 2-million-node social graph, igraph's Leiden completes in under 30 seconds on a single core, making it practical for offline batch processing pipelines.

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.

Community Evaluation Metrics

Knowing how to evaluate a community detection result is as important as knowing how to run the algorithm. Different metrics capture different notions of what makes a "good" community, and the right choice depends on whether you have ground-truth labels available.

External Validation (Ground-Truth Known)

When the true community labels are known — common in benchmarking, less common in production — two metrics dominate:

Metric	Range	Description	Scale Sensitivity
NMI (Normalised Mutual Information)	[0, 1]	Measures the information overlap between the predicted and ground-truth partitions. 1 = perfect agreement.	Robust
ARI (Adjusted Rand Index)	[-1, 1]	Compares pairwise agreements between partitions, corrected for chance. 0 = random, 1 = perfect.	Robust

NMI is generally preferred for comparing partitions with different numbers of communities, as it is less biased toward partitions with many small groups. ARI is more interpretable for practitioners familiar with classification metrics — it behaves analogously to Cohen's kappa for clustering.

from sklearn.metrics import normalized_mutual_info_score, adjusted_rand_score

ground_truth = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]  # true communities
predicted  = [0, 0, 0, 0, 1, 1, 1, 1, 1, 1]   # algorithm output

nmi = normalized_mutual_info_score(ground_truth, predicted)
ari = adjusted_rand_score(ground_truth, predicted)
print(f"NMI: {nmi:.4f}, ARI: {ari:.4f}")

Internal Validation (No Ground Truth)

In production, you rarely have ground-truth community labels. Internal validation metrics assess community quality from the graph structure alone:

• Modularity: The de facto standard — compares edge density inside communities against a random null model. Scores above 0.3 indicate meaningful structure, but modularity has a known resolution bias favouring larger communities. Always pair modularity with a secondary metric.
• Conductance: Measures the fraction of edges that cross from a community to the rest of the graph. Lower is better — a well-separated community should have few external edges. Conductance is the only metric that correlates consistently with human-judged community quality across multiple domains.
• Coverage: The fraction of intra-community edges out of all edges. Intuitively simple but trivially maximised by putting all nodes in one community — never use it alone.

Metric	Range	What It Captures	Limitation
Modularity	[-0.5, 1]	Internal density vs random baseline	Resolution limit
Conductance	[0, 1]	Boundary cut quality (lower = better)	Favours small communities
Coverage	[0, 1]	Fraction of internal edges	Trivially maximised

Recommendation: Report modularity and conductance together. A community structure with modularity > 0.4 and mean conductance < 0.2 is almost certainly meaningful. If modularity is high but conductance is also high (many cross-community edges), re-run with a higher resolution parameter.

Overlapping Community Detection

All algorithms covered so far — Louvain, Leiden, LPA — assign every node to exactly one community. They produce a partition. But real-world graphs are rarely partitionable: a person belongs to their family, their workplace, and their hobby group simultaneously. K-Clique percolation (covered above) handles this but is computationally expensive. Two additional approaches are worth knowing:

BigClam (Cluster Affiliation Model for Big Networks) models the graph as generated by node-community membership strengths. Each node has a non-negative affiliation weight for each community; the probability of an edge between two nodes increases with their shared community affiliations. BigClam scales to graphs with hundreds of thousands of nodes and millions of edges, and it produces soft membership (a node can belong to multiple communities with varying degrees). The implementation is available in the graph-tool library and the Stanford Network Analysis Platform (SNAP).

NMF (Non-negative Matrix Factorisation) factorises the graph's adjacency matrix into a product of lower-dimensional matrices, where the latent dimensions correspond to overlapping communities. NMF-based community detection is well-suited to graphs with clear block structure and produces intuitively interpretable membership vectors. Its main limitation is scalability — exact NMF is computationally intensive for graphs beyond 100,000 nodes, though stochastic variants address this.

In practice, a common production pattern is to run Leiden first to obtain a hard partition at scale, then apply BigClam or K-Clique within individual large communities to resolve overlapping structure where it matters most.

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.

Further Reading

• Graph Algorithms with Neo4j GDS — PageRank, shortest path, and centrality algorithms with production deployment patterns for the Neo4j Graph Data Science library.
• Graph Algorithms in Practice: Production Neo4j GDS — Advanced GDS patterns including algorithm chaining, incremental projections, and memory management at scale.
• Graph-Powered OSINT — How community detection, centrality, and pathfinding algorithms are applied in intelligence analysis workflows.
• Knowledge Graph Construction from Unstructured Data — Build the entity graphs that feed into community detection pipelines using LLMs and Neo4j GraphRAG.
• Introduction to GraphRAG — How Leiden-based hierarchical community summarisation powers GraphRAG's two-tier retrieval architecture.
• Traag, V. A., Waltman, L., & van Eck, N. J. From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports, 9(1), 5233, 2019. — The original Leiden paper proving the refinement phase guarantees connected communities.
• Blondel, V. D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. Fast unfolding of communities in large networks. Journal of Statistical Mechanics, P10008, 2008. — The original Louvain paper, still the most cited community detection publication.
• Yang, J. & Leskovec, J. Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach. WSDM, 2013. — The BigClam paper introducing scalable overlapping community detection via node-affiliation models.