Community Detection: Prefer Leiden, and Check What It Returns

By Sergey Nosov

16 October 2026

Run the Louvain algorithm a thousand times on the small graph below, with a different random seed each time. About one run in four returns a community in two pieces. Six nodes share one label, but no edge joins nodes 1, 2, and 3 to nodes 4, 5, and 6. With NetworkX 3.7, I counted 246 such runs. The Leiden algorithm, published in 2019 to rule that outcome out, returned none in the same thousand runs with NetworkX. The Leiden function in python-igraph 1.0.0, asked for modularity with the same edge weights, returned 232.

Louvain’s answer: pink is one community, in two pieces. Line thickness shows edge weight: 3, 2, or 1. 0 1 2 3 4 5 6 7 8 9 10

My advice fits in the title. Prefer Leiden to Louvain, and check what your library returns, because the guarantee belongs to the algorithm, not to every implementation of it. A tested C# program replays the failure, and a short Python script checks what a library returns. Later sections cover library defaults, the options from .NET, and why tools built on large language models adopted Leiden. I ran the code on .NET 10 and Python 3.12 in October 2026.

Community detection finds groups of nodes that are densely connected to one another and sparsely connected to the rest of a graph. It is unsupervised: nobody hands the algorithm a right answer. The algorithm proposes a structure, and it is up to you to judge whether that structure means anything. Some properties, though, can be checked outright, and the most basic is connectivity: the members of a community should be able to reach one another without leaving it.

What a Community Is

A graph is nodes joined by edges. The nodes can be people, bank accounts, services, cells, repositories, or source files; the edges carry the meaning, such as who paid whom or which module calls which. In their 2002 paper, Michelle Girvan and Mark Newman described community structure as nodes “joined together in tightly knit groups, between which there are only looser connections.” The technique is useful wherever relationships say more than attributes:

Scoring a Split: Modularity

If nobody knows the right answer, an algorithm needs a score to climb. The most common one is modularity, which Newman and Girvan proposed in 2004. For an undirected graph whose edges carry weights (an unweighted edge counts as 1), it reads:

Q = Σ over communities c of
    L(c) / m − (K(c) / 2m)²

Here L(c) is the total weight of the edges inside community c, K(c) is the sum of its nodes’ weighted degrees, and m is the total weight of all edges. The first term is the share of the graph’s edge weight that falls inside c. The second is the share you would expect there if the same nodes, each keeping its weighted degree, were wired at random. A weight should say how strongly two nodes are tied, not how far apart they are. Directed graphs need a directed variant, which leidenalg, for one, supports.

Newman and Girvan gave a rule of thumb for reading the number. A split no better than random scores 0, and values approaching the maximum of 1 indicate strong community structure. They add, “In practice, values for such networks typically fall in the range from about 0.3 to 0.7. Higher values are rare.” Treat the range as a hint, not a test.

The same year, Roger Guimera and colleagues showed that random graphs, built with no communities at all, score high too. Through chance fluctuations alone, “the modularity of a random graph can be as large as that of a graph with modular structure imposed at the onset.” In 2010 Benjamin Good, Yves-Alexandre de Montjoye, and Aaron Clauset found that modularity “typically admits an exponential number of distinct high-scoring solutions and typically lacks a clear global maximum.” A high score alone does not show that the groups are more than chance, still less that they mean what you hope.

The score also has a blind spot. Santo Fortunato and Marc Barthelemy showed that “modularity optimization may fail to identify modules smaller than a scale which depends on the total size of the network and on the degree of interconnectedness of the modules, even in cases where modules are unambiguously defined.” In a large graph, small but genuine communities can be merged into bigger ones.

Most implementations therefore take a resolution parameter, usually written γ, that multiplies the second term: higher values produce more and smaller communities, lower values fewer and larger ones. No single value suits every scale at once. Andrea Lancichinetti and Fortunato found that multiresolution modularity shows “the tendency to merge small subgraphs, which dominates when the resolution is low; the tendency to split large subgraphs, which dominates when the resolution is high.”

A common alternative objective is the Constant Potts Model (CPM), introduced in 2011 by Vincent Traag, Paul Van Dooren, and Yurii Nesterov. CPM compares each community with a fixed density instead of with a random graph. Its resolution works as a threshold, the density a community should reach, and CPM does not suffer from the resolution limit that Fortunato and Barthelemy described.

A Family of Algorithms

Finding the partition with the highest modularity is NP-hard, as the Leiden paper notes, so methods for large graphs rely on heuristics, and not every method uses modularity at all. Five members of the family come up most often:

Spectral methods and stochastic block models are two more major families. Fortunato and Darko Hric’s user guide from 2016 surveys them and the older methods above. The rest of this article follows the modularity line from Louvain to Leiden.

How Louvain Works

Vincent Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre published the Louvain method in 2008. It repeats two phases:

  1. Local moving. Every node starts in a community of its own. The algorithm visits the nodes one at a time and moves each one into the neighboring community that raises modularity the most, but only if the gain is positive. It keeps sweeping until no single move helps.
  2. Aggregation. Each community becomes one node of a new, smaller graph. The edges between two communities add up to one weighted edge, and the edges inside a community become a self-loop. Then phase 1 runs again on the smaller graph.

The passes stop when modularity stops rising, and along the way they build a hierarchy of communities of communities, from fine to coarse. The method is fast. The authors report that identifying communities “in a 118 million nodes network took only 152 minutes” and that simulations “suggest that its complexity is linear on typical and sparse data.” They also note that “the output of the algorithm depends on the order in which the nodes are considered,” which is why libraries shuffle the order and take a seed.

The gain of moving a node v, alone in its own community, into a community C has a closed form, which keeps each step cheap:

ΔQ = k(v,C) / m
     − k(v) · K(C) / 2m²

Here k(v,C) is the weight of v’s edges into C, and k(v) is v’s weighted degree. To move v between communities, take it out of its own community first, then compare the gains of the candidates, including the one it came from. Test such code against a brute-force recomputation of Q, because the gain is easy to get wrong by a factor of two. The expression in the arXiv version of the 2008 paper, read with each link inside C counted once, halves the first term. So does the formula in NetworkX’s documentation, although NetworkX’s code gets it right.

The Flaw: A Community in Two Pieces

In 2019 Traag, Waltman, and van Eck reported that Louvain “has a major defect that largely went unnoticed until now: the Louvain algorithm may yield arbitrarily badly connected communities. In the worst case, communities may even be disconnected, especially when running the algorithm iteratively.”

A node can hold its community together by bridging two parts of it. Once enough of its neighbors elsewhere have formed a community of their own, moving the bridge there raises modularity, so Louvain moves it. The nodes left behind stay, still well attached to their own half. Louvain moves one node at a time, so it never considers splitting the remainder. Aggregation then turns the broken community into a single node. As the paper puts it, “When a disconnected community has become a node in an aggregate network, there are no more possibilities to split up the community.”

The graph at the top of this article shows it happen. It has the shape of the paper’s own example, whose numbers use CPM; mine uses modularity. Node 0 bridges hub 1, with leaves 2 and 3, and hub 4, with leaves 5 and 6, through edges of weight 3. It also links with weight 2 to nodes 7 to 10, which link to one another with weight 1.

The C# program below runs Louvain’s first phase with the nodes visited in a fixed order, as an unlucky shuffle would visit them. It is a file-based app, shown in three blocks. Paste them in order into one file named louvain-flaw.cs in a folder of its own, and run dotnet run louvain-flaw.cs on .NET 10.

List<(int U, int V, double W)> edges =
[
    (0, 1, 3), (0, 4, 3),
    (1, 2, 1), (1, 3, 1),
    (4, 5, 1), (4, 6, 1),
];
for (int x = 7; x <= 10; x++)
{
    edges.Add((0, x, 2));
    for (int y = x + 1; y <= 10; y++)
        edges.Add((x, y, 1));
}

var graph = new Graph(11, edges);

// Louvain's first phase, with the
// nodes visited in a fixed order
int[] order = [1, 4, 2, 3, 5, 6, 7, 8, 9, 10, 0];
int[] community = graph.LocalMoving(order);
graph.Print(community);

// Split each community into its
// connected parts and score again
int[] parts = graph.ConnectedParts(community);
graph.Print(parts);

The graph class keeps an adjacency list, each node’s weighted degree, and the total weight m. LocalMoving is phase 1. It takes each node out of its community, adds up the weight of the node’s edges into each neighboring community, and moves the node where the gain is largest. Gain is the formula above multiplied by m, which does not change which move wins.

sealed class Graph
{
    readonly List<(int To, double W)>[] links;
    readonly double[] degree;
    readonly double m;

    public Graph(int n, List<(int U, int V, double W)> edges)
    {
        links = new List<(int, double)>[n];
        degree = new double[n];
        for (int v = 0; v < n; v++)
            links[v] = [];
        foreach (var (u, v, w) in edges)
        {
            links[u].Add((v, w));
            links[v].Add((u, w));
            degree[u] += w;
            degree[v] += w;
            m += w;
        }
    }

    public int[] LocalMoving(int[] order)
    {
        int n = links.Length;
        int[] community = new int[n];
        double[] total = new double[n];
        for (int v = 0; v < n; v++)
        {
            community[v] = v;
            total[v] = degree[v];
        }

        bool moved = true;
        while (moved)
        {
            moved = false;
            foreach (int v in order)
            {
                int from = community[v];
                total[from] -= degree[v];

                var weightTo = new Dictionary<int, double>();
                foreach (var (u, w) in links[v])
                {
                    int c = community[u];
                    weightTo[c] = weightTo.GetValueOrDefault(c) + w;
                }

                double Gain(int c) =>
                    weightTo.GetValueOrDefault(c)
                    - degree[v] * total[c] / (2 * m);

                int best = from;
                foreach (int c in weightTo.Keys)
                    if (Gain(c) > Gain(best))
                        best = c;

                total[best] += degree[v];
                if (best != from)
                {
                    community[v] = best;
                    moved = true;
                }
            }
        }
        return community;
    }

The rest of the class scores a partition and splits each community into its connected parts, with a depth-first search that never leaves the community it started in:

    public double Modularity(int[] community)
    {
        var inside = new Dictionary<int, double>();
        var total = new Dictionary<int, double>();
        for (int v = 0; v < links.Length; v++)
        {
            int c = community[v];
            total[c] = total.GetValueOrDefault(c) + degree[v];
            foreach (var (u, w) in links[v])
                if (community[u] == c)
                    inside[c] = inside.GetValueOrDefault(c) + w / 2;
        }
        return total.Keys.Sum(c =>
            inside.GetValueOrDefault(c) / m
            - Math.Pow(total[c] / (2 * m), 2));
    }

    // Splits every community into
    // its connected parts
    public int[] ConnectedParts(int[] community)
    {
        int[] part = new int[links.Length];
        Array.Fill(part, -1);
        int next = 0;
        for (int s = 0; s < links.Length; s++)
        {
            if (part[s] >= 0)
                continue;
            part[s] = next;
            var stack = new Stack<int>([s]);
            while (stack.Count > 0)
            {
                int v = stack.Pop();
                foreach (var (u, _) in links[v])
                    if (part[u] < 0 && community[u] == community[s])
                    {
                        part[u] = next;
                        stack.Push(u);
                    }
            }
            next++;
        }
        return part;
    }

    public void Print(int[] community)
    {
        int[] part = ConnectedParts(community);
        var groups = Enumerable.Range(0, links.Length)
            .GroupBy(v => community[v]);
        foreach (var group in groups)
        {
            string members = string.Join(", ", group);
            bool whole = group.Select(v => part[v]).Distinct()
                .Count() == 1;
            string state = whole ? "connected" : "disconnected";
            Console.WriteLine($"{{{members}}} {state}");
        }
        Console.WriteLine($"Q = {Modularity(community):F4}");
    }
}

The output:

{0, 7, 8, 9, 10} connected
{1, 2, 3, 4, 5, 6} disconnected
Q = 0.1632
{0, 7, 8, 9, 10} connected
{1, 2, 3} connected
{4, 5, 6} connected
Q = 0.2057

Here is what happened. Hubs 1 and 4 joined node 0 first, because their heavy edges to it outweighed their light ones to the leaves, and the four leaves then followed their hubs. Nodes 7 to 10 formed their own group. When node 0 finally came up, joining that group gained more than staying with the hubs, so it left. Each hub still had its two leaves in the old community, and that kept it there, while the leaves had no neighbor anywhere else. So {1, 2, 3, 4, 5, 6} stays one community whose two halves never touch.

The second printout shows the cost. Split the broken community into its two connected parts, and modularity rises from 0.1632 to 0.2057. Splitting disconnected communities after the fact is only a patch. As the paper says, “Trying to fix the problem by simply considering the connected components of communities is unsatisfactory because it addresses only the most extreme case and does not resolve the more fundamental problem.” A community can also be connected, but only in what the paper calls “a very weak sense,” and still be worth splitting.

How common is the problem? The example was built to show the flaw, so its one-in-four rate says little about real networks; the paper’s numbers are the better guide. On its six real networks, Louvain’s first iteration left 23 percent of the communities badly connected on one network and 14 to 16 percent on two others. Disconnected ones were, in the paper’s words, “usually around 1%.”

Running Louvain again from its own result, a common way to raise the score, made things worse. In the authors’ words, “Perhaps surprisingly, iterating the algorithm aggravates the problem, even though it does increase the quality function.” Disconnected communities reached 16 percent on one network, and badly connected ones 25 percent on another. Because so few communities are disconnected after the first iteration, the authors suggest, “the problem may have escaped attention from users of the algorithm.”

What Leiden Changes

Traag, Waltman, and van Eck, of Leiden University, named their algorithm after their own location, as Louvain’s authors had. It keeps Louvain’s skeleton and changes two things.

First, local moving uses a queue. The authors note that Louvain “keeps visiting all nodes in a network until there are no more node movements that increase the quality function.” After the first pass over all nodes, Leiden revisits only the nodes whose neighborhood changed. When a node moves, its neighbors outside its new community go to the back of the queue.

Second, a refinement phase runs between local moving and aggregation. Within each community that local moving found, refinement starts again from single nodes and merges them into pieces, but only when both sides are well connected to that community. Leiden then aggregates the pieces, not the communities, and each piece starts the next level in the community it came from. A community that lost its bridge therefore reaches the next level as separate nodes, and the next round of local moving can pull them apart.

A node that is still alone joins a piece only if the merge does not lower the score. With a positive resolution, even a merge that leaves the score unchanged takes at least one edge between the node and the piece, so every refined piece is connected. Refinement does not always take the best merge. It picks at random among the merges that do not lower the score, favoring larger gains. A parameter θ sets how random the choice is; the paper’s experiments used 0.01.

The randomness is not what keeps communities connected; merging only within a community, one connected node at a time, does that. The authors give the randomness another purpose: “Randomness in the selection of a community allows the partition space to be explored more broadly.”

The guarantees come with proofs. After every iteration, each community is connected, in a slightly stronger sense the paper calls γ-connected. Run iteratively, Leiden converges to a partition in which “all subsets of all communities are locally optimally assigned.” No subset of a community can then raise the score by moving to another community or by splitting off on its own. The authors also report that Leiden finds better partitions and runs faster, up to twenty times faster than Louvain on their real networks. Their verdict: “the Leiden algorithm is strongly preferable to the Louvain algorithm.”

One caveat cuts the other way. Connectivity holds after every iteration, but the stronger properties take more iterations. The paper reports that “in terms of the percentage of badly connected communities in the first iteration, Leiden performs even worse than Louvain.” From the second iteration on, Leiden did better. Both leidenalg and python-igraph default to two iterations, so ask for more when quality matters.

Check What Your Library Returns

Leiden, the algorithm, cannot return a disconnected community; a library can. Four checks are worth making before you trust a partition.

The objective. The community_leiden method in python-igraph and the leiden_communities function in NetworkX both default to CPM with a resolution of 1, not to modularity. On a simple unweighted graph, CPM at that resolution charges as much for each pair of nodes in a community as an edge between them can earn. No merge ever raises the score. Run either one with its defaults on an unweighted copy of Zachary’s karate club, a classic social network of thirty-four people, and you get thirty-four communities of one member each.

Ask for modularity (objective_function="modularity" in python-igraph, metric="modularity" in NetworkX), and you get four communities. NetworkX’s own karate_club_graph() carries edge weights, and on it the defaults return seventeen to nineteen communities, eleven to fourteen of them single members, depending on the seed. In leidenalg the partition type is a required argument, and Neo4j’s implementation maximizes modularity. Wherever you run it, name the objective and the resolution explicitly.

Connectivity. The check takes a few lines. This Python script runs both NetworkX algorithms on the example graph with a thousand seeds and counts the runs that return a disconnected community:

import itertools

import networkx as nx
from networkx.algorithms.community import (
    leiden_communities, louvain_communities)

G = nx.Graph()
G.add_weighted_edges_from(
    [(0, 1, 3), (0, 4, 3), (1, 2, 1), (1, 3, 1),
     (4, 5, 1), (4, 6, 1)]
    + [(0, x, 2) for x in range(7, 11)]
    + [(x, y, 1) for x, y
       in itertools.combinations(range(7, 11), 2)])


def disconnected(G, communities):
    return [c for c in communities
            if not nx.is_connected(G.subgraph(c))]


seeds = range(1000)
louvain = sum(
    bool(disconnected(G, louvain_communities(G, seed=s)))
    for s in seeds)
leiden = sum(
    bool(disconnected(G, leiden_communities(
        G, metric="modularity", seed=s)))
    for s in seeds)
print(louvain, leiden)

The script needs NetworkX 3.7: in versions 3.5 to 3.6.1, leiden_communities exists only as a hook for other backends and raises NotImplementedError. With NetworkX 3.7, it prints:

246 0

Louvain broke the community apart in 246 runs and Leiden in none. Louvain in python-igraph, community_multilevel, did it in 260, given the same edge weights.

NetworkX’s Leiden had a weakness of its own. In 147 runs it returned nodes 1 to 6 in four smaller pieces, such as {1, 3}, {2}, {4, 5}, and {6}. All are connected, but they score 0.1328, lower than Louvain’s broken answer at 0.1632, and merging {2} into {1, 3} would raise the score. The cause is what it returns. NetworkX hands back the pieces from the refinement step of its last level. The paper’s algorithm returns the communities from a final round of local moving, which can still merge such pieces. Connected is not the same as good.

Then python-igraph 1.0.0, the current release in October 2026, surprised me. Asked for modularity and given the edge weights, its community_leiden returned a disconnected community for 232 of the same thousand seeds. It uses edge weights only when you pass them, as in weights="weight". Three, ten, or a hundred iterations returned the same broken partition. According to the documentation, a negative count such as n_iterations=-1 will “run until a stable iteration is encountered.” With it, none of those 232 seeds returned within ten seconds, while the other 768 returned in under a millisecond.

Both symptoms match igraph issue #2934, reported on 28 September 2026. The pull request that fixed the issue gives a cause that fits both. Moves made on the last aggregation level were dropped, it says, so the returned clustering “could then contain disconnected clusters.” With a negative iteration count, it adds, “every iteration repeated the same moves, so the call never returned.” The fix was merged into igraph’s main branch on 30 September 2026. As of mid-October, no release of the C library or of python-igraph includes it.

I did not build the patched library, but a cheap test points the same way. Started from the broken partition, python-igraph handed it back unchanged for all 200 seeds I tried, while leidenalg, given two iterations, split it every time.

The authors’ own Python package, leidenalg 0.12.0, did better, though not perfectly. With ModularityVertexPartition, the edge weights, and its default of two iterations, one seed in a thousand, seed 35, returned the same broken community. That run’s first iteration had produced a connected partition. The second moved node 0 out and stopped there, and a third iteration repaired the damage. Yet the package’s documentation lists γ-connectivity among the guarantees that hold “after each iteration.” With n_iterations=-1, none of the thousand seeds failed.

The lesson is not that one library is good and another bad. A guarantee proved for an algorithm reaches you through code that someone wrote, with defaults that someone chose. Checking connectivity takes time proportional to the size of the graph, so run it on every partition you rely on.

Stability. Louvain and Leiden are randomized, and as the user guide puts it, “Many clustering techniques are stochastic in character and do not deliver a unique answer.” Fix the seed so that a run can be repeated, and pin the library version. Microsoft’s GraphRAG, discussed below, does much the same. Its configuration fixes the clustering seed by default, and its package keeps graspologic-native, the Rust Leiden library it calls, on the 1.2 line, below version 1.3. A comment in its repository gives the reason: “graspologic-native 1.3.x changes Leiden clustering output (community counts/levels).”

Then vary the seed on purpose. If the grouping changes a lot with the seed, do not treat any one partition as settled. The variation may reflect weak structure, several partitions that score almost the same, or a search that stops early. Consensus clustering, which the user guide describes, combines many runs into one partition.

Meaning. Finally, validate against something you know, such as labels for a sample of nodes, a domain expert’s reading, or a downstream measure. The Leiden paper warns that in biological networks, badly connected communities “may lead to incorrect attributions of shared functionality.” Any community you act on deserves the same suspicion.

Leiden from .NET

I found no widely used .NET implementation of Leiden. A NuGet search for “leiden” in October 2026 returned three packages, and the one that names Leiden community detection in its description had about two hundred downloads. A .NET application has three practical routes:

The local-moving loop above is the easy part, which is why it fits in an article. The guarantees depend on the refinement phase and on the bookkeeping around it, and the igraph bug was a slip in that bookkeeping, not in the refinement itself. If you write your own anyway, test it on hundreds of random graphs, against a brute-force recomputation of the score and a connectivity check, as I tested the sample above.

Why Language-Model Tools Picked Up Leiden

A 2019 result from network science found a second career in retrieval-augmented generation. Darren Edge and colleagues describe Microsoft’s GraphRAG in a paper, quoted here from its February 2025 revision. A language model extracts entities and relationships from a document collection into a knowledge graph. The pipeline then uses, in the paper’s words, “Leiden community detection (Traag et al., 2019) in a hierarchical manner, recursively detecting sub-communities within each detected community until reaching leaf communities that can no longer be partitioned.”

Note the direction. Louvain’s hierarchy grows bottom-up, from its aggregation passes. GraphRAG’s grows top-down. Its current code calls the hierarchical Leiden function of graspologic-native. As graspologic documents it, that function runs Leiden on the whole graph and then again inside every community that is still larger than a size limit. GraphRAG sets that limit at ten members by default, though a community stays larger if Leiden cannot split it further.

A language model summarizes every community, and questions about the whole collection, such as its main themes, are answered from those summaries, not the raw text. The hierarchy is what makes such queries cheap. In the GraphRAG paper’s tests, answering from the root-level summaries “required over 97% fewer tokens” of context than map-reduce summarization of the source texts. Building the graph and its summaries is a separate, up-front cost. The authors weigh the saving against “a modest drop in performance compared with other global methods,” and root-level answers still beat vector retrieval on comprehensiveness and diversity.

A Microsoft Research post from November 2024 added dynamic community selection. Starting at the root, a smaller model rates each community’s summary for relevance, and the search descends only into relevant ones. On fifty questions about a news dataset, that cut the cost by 77 percent on average against answering from all the summaries at level 1. A language-model judge rated the answers similar.

Letting the search descend to level 3 cost 34 percent more than that baseline. On the twenty-nine questions where it drew on more summaries, the judge rated its answers more comprehensive and more empowering. The levels of the hierarchy work as a dial between cost and depth.

Whether a graph beats plain vector retrieval for your questions is a separate matter, and independent studies are mixed; my article on knowledge graphs covers that evidence. Not every graph-based retriever clusters, either. HippoRAG, for one, runs Personalized PageRank over its knowledge graph, starting from the concepts in the question. And the GraphRAG repository itself now describes the project as “largely in maintenance mode,” with bug fixes and dependency updates still promised.

Takeaways

In the Metaphysics, as W. D. Ross translated it, Aristotle separates “a mere heap” from a whole that “is something beside the parts,” and for bodies he names what makes such a whole one: “contact is the cause of unity in some cases.” In a graph, contact is an edge. A community that comes back in two pieces is a heap with a shared label. Leiden was designed so that every community is a whole, and a short check confirms that your library delivered one. The value was never in the nodes. It is in the edges.

Further Reading