liveBook · Manning

Leiden algorithm

As explained in Retrieval Augmented Generation, The Foundational Ideas

The Leiden algorithm is a community-detection algorithm that iteratively optimizes a graph partition while refining communities into internally connected groups.

The Leiden algorithm detects coherent graph communities by optimizing modularity while preserving internal connectivity. It is useful when groups must be summarized or processed as connected units rather than as arbitrary node sets. section 12.2.1

Its community-detection loop proceeds as follows:

  • Start with every node in its own community. section 12.2.1
  • Move nodes between communities when the move improves modularity, which compares internal connectivity with a random-edge baseline. section 12.2.1
  • Refine communities by splitting disconnected sub-clusters introduced during node movement. section 12.2.1
  • Aggregate each community into a super-node and repeat until modularity no longer improves. section 12.2.1

Internal connectivity is the practical distinction: every returned community has a path between any two members using only edges inside that community. GraphRAG can therefore pass each group to an LLM for summarization. section 12.2.1

A Python indexing pipeline commonly builds the graph with NetworkX, converts it to igraph, runs the mature Leiden implementation through leidenalg, and maps the resulting clusters back to NetworkX node IDs. This separates graph construction from clustering while retaining the downstream graph representation. section 12.2.3

Listing 12.2 Community detection.
import igraph as ig
import leidenalg
 
def detect_communities(self) -> Dict[int, List[str]]:
    """Apply Leiden algorithm to detect communities."""
    g_ig = ig.Graph.from_networkx(self.graph)  #A
 
    partition = leidenalg.find_partition(  #B
        g_ig,
        leidenalg.ModularityVertexPartition,
        weights='weight',
        n_iterations=-1
    )
 
    self.communities = {}  #C
    for idx, cluster_nodes in enumerate(partition):
        node_labels = [
            g_ig.vs[i]['_nx_name'] for i in cluster_nodes  #D
        ]
        self.communities[idx] = node_labels
 
    return self.communities
 

The listing shows modularity-based partitioning with leidenalg, weighted edges, unlimited iterations, and conversion of partition members back into node labels. section 12.2.3

How Retrieval Augmented Generation, The Foundational Ideas covers it

How deep it goes
Explains the iterative partition, refinement, aggregation, and stopping process, then demonstrates Python integration without deriving modularity mathematically.
Examples
Uses GraphRAG community summarization and a Python pipeline that converts NetworkX graphs into igraph partitions.
What it assumes
Assumes a constructed graph with nodes and relationships; teaches the clustering loop and library handoff explicitly.
What you can do after
Apply it via igraph and leidenalg to partition a weighted graph and recover communities as NetworkX node identifiers.
How it connects
Connects modularity, graph partitioning, GraphRAG, hierarchical communities, igraph, NetworkX, and Louvain.

Also explained in

Compare how 2 books explain Leiden algorithm →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Retrieval Augmented Generation, The Foundational Ideas. The section links point to the parts of the book it draws on.