Label spreading

The last algorithm (proposed by Zhou et al.) that we need to analyze is called label spreading, and it's based on the normalized graph Laplacian:

This matrix has each a diagonal element l_ii equal to 1, if the degree deg(l_ii) > 0 (0 otherwise) and all the other elements equal to:

The behavior of this matrix is analogous to a discrete Laplacian operator, whose real-value version is the fundamental element of all diffusion equations. To better understand this concept, let's consider the generic heat equation:

This equation describes the behavior of the temperature of a room when a point is suddenly heated. From basic physics concepts, we know that heat will spread until the temperature reaches an equilibrium point and the speed of variation is proportional to the Laplacian of the distribution. If we consider a bidimensional grid at the equilibrium...