Spectrum of the (normalized) Laplacian and graph partitioning. Consider an undirected and unweighted network graph G(V, E), with order N_v, : = |V|, size N_e" = |E|, and adjacency matrix A. Let D = diag (d_1, ..., d_N_v) be the degree matrix and L: = D- A the Laplacian of G. An alternative form of the Laplacian known as the normalized Laplacian is defined as L: = D^-1/2 LD^-1/2 = I - D^-1/2 AD^-1/2 Both L and L can be shown to have non-negative eigenvalues, and minimal eigenvalue equal to 0 with corresponding eigenvectors 1: [1, ..., 1]^T and D^1/2 1 = [Squareroot d_1, ..., Squareroot d_n_v]^T respectively. Moreover the eigenvalues of L can be shown to fall in the interval [0, 2]. For the graph in Fig. 1, compute L and L and verify numerically that the aforementioned properties hold For a connected G, the second smallest eigenvalue of L and L will be nonzero, and its corresponding eigenvector is often found to be useful for partitioning G in two cohesive sub graphs. A simple approach is to annotate each vertex in G with the sign of the corresponding entry in this eigenvector. e will later study and justify this and other approaches useful for network community detection. Try it for the graph in Fig, 1. Is the graph partitioned in a sensible manner? If time allows, try modifying the graph in Fig. 1 by adding and deleting edges and vertices and repeating parts A and B). How do the eigenvalues and the eigenvector corresponding to the first non- zero eigenvalue behave under these changes? What happens if your graph becomes disconnected? Spectrum of the (normalized) Laplacian and graph partitioning. Consider an undirected and unweighted network graph G(V, E), with order N_v, : = |V|, size N_e" = |E|, and adjacency matrix A. Let D = diag (d_1, ..., d_N_v) be the degree matrix and L: = D- A the Laplacian of G. An alternative form of the Laplacian known as the normalized Laplacian is defined as L: = D^-1/2 LD^-1/2 = I - D^-1/2 AD^-1/2 Both L and L can be shown to have non-negative eigenvalues, and minimal eigenvalue equal to 0 with corresponding eigenvectors 1: [1, ..., 1]^T and D^1/2 1 = [Squareroot d_1, ..., Squareroot d_n_v]^T respectively. Moreover the eigenvalues of L can be shown to fall in the interval [0, 2]. For the graph in Fig. 1, compute L and L and verify numerically that the aforementioned properties hold For a connected G, the second smallest eigenvalue of L and L will be nonzero, and its corresponding eigenvector is often found to be useful for partitioning G in two cohesive sub graphs. A simple approach is to annotate each vertex in G with the sign of the corresponding entry in this eigenvector. e will later study and justify this and other approaches useful for network community detection. Try it for the graph in Fig, 1. Is the graph partitioned in a sensible manner? If time allows, try modifying the graph in Fig. 1 by adding and deleting edges and vertices and repeating parts A and B). How do the eigenvalues and the eigenvector corresponding to the first non- zero eigenvalue behave under these changes? What happens if your graph becomes disconnected
