Skip to content

LearnGraphs & hierarchy

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).

Sources

Jump to