Label spreading

Another algorithm (proposed by Zhou et al.) that we need to analyze is called label spreading, which offers a slight better stability when the dataset is very noisy or dense. In these cases, standard label propagation might suffer a loss of precision due to the closeness of points with different labels. Conversely, label spreading is more robust because the Laplacian is normalized and abrupt transitions are more heavily penalized (all mathematical details are quite complex, but the reader can find all details in Biyikoglu T., Leydold J., Stadler P. F., Laplacian Eigenvectors of Graphs, Springer, 2007).

The algorithm is based on the normalized graph Laplacian, defined as:

Considering it in matrix form, it has a diagonal element equal to 1, if the degree (0 otherwise), and all the other elements equal to:

This operator is a particular case of a generic graph Laplacian:

The behavior of such an operator is analogous to a discrete Laplacian...