The Leiden algorithm detects communities in a graph by optimizing modularity. It begins with each node in its own community, moves nodes to improve the score, refines the resulting partition, aggregates communities into a new network, and repeats until improvement stops. section 14.1
It improves on Louvain by refining communities before aggregation, addressing Louvain’s possibility of producing internally disconnected communities. NetworkX does not provide Leiden directly, so a simple pure-Python implementation can supply the missing step. section 14.1
A practical Leiden pass follows this sequence:
- Initialize a singleton partition with one community per graph node. section 14.1
- Evaluate moving each node into neighboring communities using modularity gain, retaining moves that improve the partition. section 14.1
- Refine the partition, aggregate nodes belonging to the same community, and repeat for a bounded number of iterations or until no improvement remains. section 14.1
Community detection in GraphRAG
After extracted entities and relationships are merged into a NetworkX graph, Leiden assigns community identifiers. The resulting groups can be converted into node lists, summarized as related document groups, and used by global search to produce intermediate answers before combining them into a final response. section 14.1 section 14.4
