The algorithm of Label Propagation (synchronous update) is as follows:
- Initialize the labels at all nodes in the network. For a given node \(x\), \(C_{x}\left ( 0 \right )=x\).
- Set \(t = 1\).
- Arrange the nodes in the network in a random order and set it to \(X\).
- For each \(x\in X\) chosen in that specific order, let \(C_{x}\left ( t \right )=f\left ( C_{x_{1}}\left ( t-1 \right )+\cdots +C_{x_{k}}\left ( t-1 \right )\right )\). \(f\) here returns the label occurring with the highest frequency among neighbors and ties are broken uniformly randomly.
- If every node has a label that the maximum number of their neighbors have, then stop the algorithm. Else, set \(t = t + 1\) and go to (3).
For more details, please see https://arxiv.org/abs/0709.2938