Label Propagation in 2D — Community Detection by Majority Vote

Graph

Nodes 80

Planted communities 4

Mixing μ (inter-community edge share) 0.10

Label Propagation

Auto-run speed 3/s

Show ground-truth communities (ring layout)

running…

Iteration t

Distinct labels

–

Nodes changed (last step)

–

Modularity Q

–

How it works

Label Propagation (Raghavan, Albert & Kumara, 2007) finds communities without optimizing any global objective — it only looks at each node's immediate neighbourhood, which makes one full sweep run in roughly O(edges) time.

1. give every node i a unique label: label(i) = i
2. repeat, visiting nodes in random order each sweep:
     for node i:
       label(i) ← the label held by the MOST neighbours of i
                   (ties broken uniformly at random)
3. stop when no node's label changes in a full sweep

Nodes that end up sharing a label form a community — dense clusters "vote" the same label into all their members because most of a node's neighbours already agree once a cluster starts to align, so agreement spreads like an epidemic through the cluster and stalls at community borders.

Planted communities / mixing μ — the graph is generated as a stochastic block model: nodes are split into k groups laid out as separate clusters in the 2D plane, and each possible edge is kept with high probability inside a group and with probability μ across groups. Small μ ⇒ well-separated ground-truth communities; μ near 0.45 ⇒ the groups blur together and propagation struggles to recover them.
Step / Auto-run — each step is one synchronous-order sweep over every node (visited in random order, seeing labels already updated earlier in the same sweep); node colour = current label, so watch the palette collapse from N distinct colours down to roughly k as clusters agree internally.
Modularity Q — reported only as a diagnostic (Q = (1/2m)Σ[A_ij − k_ik_j/2m]δ(c_i,c_j)); unlike the Louvain method, this algorithm never optimizes Q directly, so watching it rise is a side effect, not the goal.
Drag to pan, scroll/pinch to zoom on the main panel — useful once node count is high and clusters overlap on screen. The strip chart below tracks nodes-changed and modularity across every sweep so far.
Real-world use: fraud rings in transaction graphs, fast community pre-passes on billion-edge social/web graphs, and as the seed step inside label-propagation-based semi-supervised learning.

Node colour = current label Edge = graph connection

drag to pan · scroll to zoom

Convergence history● nodes changed ● modularity Q