Label propagation
LPA
A community detection method where every node starts with its own label and repeatedly adopts the label most common among its neighbors until labels stop changing.
In DocSlurpGlossary entry
On this page
Every node starts with its own label. Node by node, each adopts the label with the most total edge weight among its neighbors. Repeat until nothing changes; nodes sharing a label form a community.
A worked example
Take two triangles, A-B-C and D-E-F, joined by one weak edge C-D of weight 0.5 (all other edges weigh 1). Visit nodes alphabetically; ties go to the alphabetically smaller label.
| Node | Neighbor labels (weight) | New label |
|---|---|---|
| A | B 1, C 1 | B (tie, smaller) |
| B | B 1, C 1 | B |
| C | B 2, D 0.5 | B |
| D | E 1, F 1, B 0.5 | E |
| E | E 1, F 1 | E |
| F | E 2 | E |
A second pass changes nothing: two communities, {A, B, C} and {D, E, F}. The weak edge never carried enough weight to pull a label across.
The gotcha
Now give C-D a weight of 1. When D’s turn comes, B, E and F tie at 1, the tie-break picks B, and E and F follow. Every node ends up labeled B: one community where you wanted two. Label propagation is sensitive to visiting order, tie-breaking and edge weights: one strong bridge can let a label sweep the graph.
DocSlurp’s variant (core/worker/src/graph/communities.ts) is deterministic: nodes are visited in id order, ties go to the smaller label, and it runs at most 20 rounds. Co-mention edges (two entities that merely share a chunk) count half as much as extracted relationships, which makes incidental links weaker bridges. Determinism lets unchanged communities keep their summaries; it does not remove the sensitivity to strong bridges.
In DocSlurp
In DocSlurp
DocSlurp runs a weighted, deterministic variant for at most 20 rounds: nodes are visited in id order, ties go to the smaller label, and co-mention edges count half as much as extracted relationships (core/worker/src/graph/communities.ts).