Label Propagation, in depth: community detection in near-linear time, a hand trace, an implementation, oscillation and flooding, variants and evaluation

The algorithm

The algorithm as published by Raghavan, Albert and Kumara in 2007 uses asynchronous updates in random order:

LABEL-PROPAGATION(G):
    for each node v: label[v] = v
    repeat:
        order = random permutation of nodes
        for v in order:
            counts = histogram of label[u] for u in neighbours(v)     # weighted: sum of w(v,u)
            best = labels with maximum count
            label[v] = random choice from best                         # ties broken uniformly at random
    until every node v has a label in its own `best` set
    return groups of nodes with equal labels

Three details carry the whole behaviour. Asynchronous means a node sees labels already updated earlier in the same pass, which lets a label sweep through a dense group in one pass. Random order and random tie-breaking avoid systematic bias towards low node ids. And the stopping rule is not "no label changed" but "every node already holds one of its most frequent neighbour labels"; with random tie-breaking, a node with a tie can flip forever even though the partition is stable, so checking for changes alone may never terminate.

Worked example: tracing two cliques

Take two 4-cliques, {A, B, C, D} and {E, F, G, H}, joined by one bridge edge D to E. Start with each node labelled by its own lower-case name. To make the trace reproducible, break ties by the alphabetically smallest label instead of at random, and use the order B, A, C, D, F, G, H, E.

In the second pass every node's label is already its most frequent neighbour label (D sees three a against one e; E sees three e against one a), so the algorithm stops with two communities. Notice how asynchrony helped: B's choice at step 1 was visible to A at step 2 and to C at step 3, so label a took the whole clique in one pass.

Now run it synchronously, every node choosing from the previous pass's labels at once, on the smallest possible graph: one edge u to v. In pass 1, u takes v's label and v takes u's. In pass 2 they swap back. The same oscillation appears on any bipartite structure, such as star-shaped subgraphs around hubs, which is why the asynchronous rule matters and why synchronous implementations need an iteration cap.

An implementation

A direct implementation for an undirected, optionally weighted graph. It takes a seed so runs are reproducible, caps the number of passes, and uses the published stopping rule.

import random
from collections import defaultdict


def label_propagation(adj, seed=0, max_passes=100):
    """adj: dict node -> dict neighbour -> weight (undirected: both directions present)."""
    rng = random.Random(seed)
    label = {v: v for v in adj}
    nodes = list(adj)

    def best_labels(v):
        score = defaultdict(float)
        for u, w in adj[v].items():
            score[label[u]] += w
        if not score:                      # isolated node keeps its own label
            return [label[v]]
        top = max(score.values())
        return [l for l, s in score.items() if s == top]

    for passes in range(1, max_passes + 1):
        rng.shuffle(nodes)
        for v in nodes:
            best = best_labels(v)
            if label[v] not in best:       # keep the current label when it is tied for best
                label[v] = rng.choice(best)
        if all(label[v] in best_labels(v) for v in nodes):
            break

    groups = defaultdict(set)
    for v, l in label.items():
        groups[l].add(v)
    return list(groups.values()), passes


edges = [("A","B"),("A","C"),("A","D"),("B","C"),("B","D"),("C","D"),
         ("E","F"),("E","G"),("E","H"),("F","G"),("F","H"),("G","H"),("D","E")]
adj = defaultdict(dict)
for a, b in edges:
    adj[a][b] = adj[b][a] = 1.0
print(label_propagation(adj))   # two groups: {A,B,C,D} and {E,F,G,H}

One deliberate change from the pseudocode: a node keeps its current label when that label is among the tied best. This damps pointless flipping between equally good labels and makes the stopping rule trigger sooner, without changing which partitions are stable. In production, replace the dictionaries with compressed sparse row arrays and integer labels; the per-node histogram is then the hot loop, and a small open-addressed hash map reused across nodes avoids allocation.

Cost

Each pass touches every edge twice, so a pass is O(m) for m edges, plus the cost of shuffling. Empirically the number of passes is small and grows slowly with graph size, which is why the original paper called it near linear; there is no useful worst-case bound on the pass count, so always set a cap. Memory is the adjacency plus one label per node. That is far less than methods that need eigenvectors, which is the practical reason label propagation is used on graphs where colouring-style or spectral approaches will not fit.

Incremental updates on changing graphs

Real graphs change: new users, new transactions, deleted edges. Re-running from unique labels every night throws away work and, worse, renames every community, so downstream systems that stored yesterday's community ids see a complete reshuffle. Two techniques fix both problems.

Warm start. Initialise each existing node with yesterday's label and each new node with its own id, then run the normal passes. Most nodes are already stable, so the first pass changes little and the run stops after very few passes. Community ids survive wherever the structure survived.

Local updates. After an edge insert or delete, only the endpoints' neighbourhoods can have a different most frequent label. Put those nodes in a queue, re-evaluate them, and enqueue a node's neighbours only when its label actually changes. This is the same idea as the queue-based fast variant below, applied to a stream of edits, and it touches a small fraction of the graph per batch.

Both still need a periodic full run from scratch, because warm starts preserve early mistakes: a giant community that formed once tends to persist. Schedule a cold run weekly, match its communities to the warm ones by overlap so ids stay stable where possible, and alert when the mapping shows large merges or splits.

Failure modes

What goes wrong, and how to detect it:

• One giant community. On graphs with weak structure or high-degree hubs, one label floods most of the graph. Check the size distribution; if the largest community holds a large fraction of nodes, the result is not informative. Hop attenuation and node-preference variants were designed for exactly this.
• Different results on every run. Order and ties are random, so communities change between runs and between library versions. Fix the seed for reproducibility, but measure stability across several seeds before trusting any single partition.
• Disconnected communities. A label can spread through a node that later switches away, leaving two separate pieces with the same label. Post-process by splitting each label's node set into connected components with union-find or a BFS.
• Oscillation in synchronous implementations. Distributed versions often update synchronously. They stop only because of the iteration cap, and the final labels then depend on whether the cap was odd or even.
• Directed graphs treated naively. Following only out-edges lets labels flow one way and pile up at sinks. Symmetrise the graph unless direction is the point.

Variants

The basic algorithm has many descendants. The ones worth knowing:

Do not confuse community-detection label propagation with the semi-supervised label propagation of Zhu and Ghahramani, which spreads known class labels from a few labelled nodes to unlabelled ones by iterating a smoothing operator. The names match; the problems and guarantees do not.

Using libraries: NetworkX and GraphFrames

You rarely need to write it yourself. NetworkX provides asyn_lpa_communities(G, weight=None, seed=None) for the asynchronous algorithm, label_propagation_communities(G) for the semi-synchronous version, and fast_label_propagation_communities in recent releases. On Spark, GraphFrames runs static (synchronous) label propagation:

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

G = nx.karate_club_graph()
for seed in range(5):
    parts = list(nxc.asyn_lpa_communities(G, seed=seed))
    print(seed, len(parts), round(nxc.modularity(G, parts), 3))

# Spark: GraphFrames returns the vertices with a new 'label' column.
# result = g.labelPropagation(maxIter=10)
# result.groupBy("label").count().orderBy("count", ascending=False).show()

Because the GraphFrames version is synchronous, choose maxIter deliberately, look at how many labels changed in the last iterations, and run the connected-component split afterwards. On billion-edge graphs, the costs are shuffles per superstep and skew from hub vertices; checkpoint long lineages, and see GraphFrames on Spark for the operational side.

Evaluating the output, and choosing a method

With no objective function, you must evaluate the output explicitly. Compute modularity of the partition and compare it with Louvain or Leiden on a sample; compute conductance for the largest communities; plot community sizes on a log scale; and measure agreement between runs with different seeds using normalised mutual information or the adjusted Rand index. If two seeds disagree heavily, the graph's structure is weak at that scale, and any downstream decision built on one run is built on noise.

A common production pattern combines them: label propagation as a fast first pass to find candidate groups or to initialise another method, and Leiden on the subgraphs that matter. Pairing it with strongly connected components on directed graphs is another cheap way to split the problem before clustering.

What to do next

1. Run asyn_lpa_communities on a sample of your graph with five seeds; record community counts, modularity and size distribution.
2. Measure NMI between seeds. If agreement is low, do not build on a single run.
3. Symmetrise directed graphs and remove or down-weight hubs that cause flooding.
4. Split every label into connected components before using the output.
5. At scale, use GraphFrames with an explicit maxIter, checkpointing, and a check on labels changed per iteration.
6. Compare against Leiden on the same sample, and choose label propagation only where its speed is needed.
7. Keep the seed, library version and parameters with every stored partition so results can be reproduced.