@graphty/algorithms / index / labelPropagation
Function: labelPropagation() ​
labelPropagation(
s,options?):LabelPropagationResult
Defined in: indexed/label-propagation.ts:396
Community detection by fast label propagation (FLPA; Traag and Subelj, Sci. Rep. 13:2701, 2023, Algorithm 3), the queue-driven form of Raghavan, Albert and Kumara's asynchronous label propagation.
Every node starts in its own community. Nodes are visited from a queue that starts as a seeded shuffle of all of them; a visited node adopts the label with the largest summed arc weight among its neighbours, drawing uniformly at random among tied labels (its current label included, with no priority). When its label changes, every neighbour holding a different label is queued again. The run ends when the queue empties -- then every node's label is dominant among its neighbours and converged is true -- or after maxIterations * nodeCount node visits.
Conventions: self-loops are skipped; parallel arcs are summed; on a directed snapshot a node's neighbours are its out-arcs AND its in-arcs, so a reciprocal pair counts twice. With weighted: false each distinct neighbour votes once. A negative, NaN or infinite weight throws. Votes use the exact f64 weights when the snapshot keeps them (as toSnapshot does for a legacy graph whose weights are not all f32-exact), so a weight rounded in the f32 arc array never decides a vote.
One randomSeed gives one result, bit for bit. The partitions differ from the legacy labelPropagation for the same seed: the random stream and the stop rule are different (design design/algorithms/label-propagation-indexed-port-design.md, section 3).
Parameters ​
s ​
GraphSnapshot
Any snapshot
options? ​
Work cap, seed and weighting
Returns ​
The partition, the full-sweep equivalents run, and whether the work queue emptied