Label Propagation is another example of a community detection algorithm. Proposed in 2017, its strength is in its possibility to set some labels for known nodes and derive the unknown labels from them in a semi-supervised way. It can also take into account both relationships and node weights. In this section, we are going to detail the algorithm with a simple implementation in Python.
Defining Label Propagation
Several variants of Label Propagation exist. The main idea is the following:
- Labels are initialized such that each node lies in its own community.
- Labels are iteratively updated based on the majority vote rule: each nodes receives the label of its neighbors and the most common label within them is assigned to the node. Conflicts appear when the most common label is not unique. In that case, a rule needs to be defined, which can be random or deterministic (like in the GDS).
- The iterative process is repeated until all nodes have fixed labels...