After the fairly theoretical previous section, we aim at giving the reader a better intuition behind the WSD with a simple example. Figure 6.2 shows a small network, called G_{1}, with seven nodes and eight links. As can be seen there are two cycles of length 3 in this network and one of length 4. We will take N = 3 in this example for convenience and without loss of generality. The random walk probabilities are labeled in Figure 6.2. For example, node 3 has a degree of 5 resulting in a probability of 1/5 th for each edge. The total probability of taking a random walk around each 3-cycle is 6 × 1/2 × 1/3 × 1/3 = 0.33, also shown in Figure.^{6}

Figure 6.3 shows a 3D plot of the absolute value (for clarity) of the eigenvectors of the normalized Laplacian. The corresponding eigenvalues are shown in Table 6.1.

The eigenvectors of the normalized Laplacian can be used to form a partitioning of the nodes in a graph. In this example, nodes 4 and 5 are grouped into eigenvector 3, nodes 1, 2, and 6 into eigenvectors ...

Start Free Trial

No credit card required