Spectral Clustring using Lapracian Matrix

What is Laplacian Matrix?

The Laplacian matrix is a matrix in graph theory that represents the connection relationships between the vertices of a graph. Specifically, it is an important tool used to analyze the structure of the graph and to understand how the graph is connected and its characteristics.

The Laplacian matrix (L) is defined as follows:

L = D - A

Where,

(A) is the adjacency matrix of the graph, which indicates the presence (or weight) of edges between each pair of vertices.
(D) is the degree matrix, a diagonal matrix that places the number of edges (or the total weight of these edges) connected to each vertex along its diagonal.

Therefore, each element (L_{i,j}) of the Laplacian matrix is represented as:

(L_{i,i} = d_i) (where (d_i) is the degree of vertex (i))
(L_{i,j} = -1) (if vertex (i) and (j) are connected, in the case of an undirected graph)
(L_{i,j} = 0) (if vertex (i) and (j) are not connected)

The properties of the Laplacian matrix include:

The sum of all rows, or the sum of all columns, of (L) is 0. This is because the input and output of edges at each vertex are balanced.
(L) is a positive semi-definite matrix, and its eigenvalues are non-negative.
The smallest eigenvalue of (L) is 0, and its multiplicity equals the number of connected components the graph has.

The Laplacian matrix is used in the spectral analysis of graphs, the synchronization of networks, graph partitioning, and many other applications.

Eigen Decomposition of Lapracian Matrix

The eigenvalue decomposition of the Laplacian matrix is a powerful tool for understanding the structural properties and behaviors of a graph. Eigenvalue decomposition involves breaking down a matrix into its eigenvalues and eigenvectors, allowing for a deeper analysis of the graph’s characteristics.

The eigenvalue decomposition of the Laplacian matrix (L) is represented in the following form:

L = U \Lambda U^T

Where,

(U) is the orthogonal matrix consisting of eigenvectors of (L), with each column corresponding to an eigenvector of (L).
(Λ) is a diagonal matrix, whose diagonal elements correspond to the eigenvalues of (L).
(U^T) is the transpose of (U).

What the eigenvalue decomposition of the Laplacian matrix signifies:

Eigenvalues: The eigenvalues of the Laplacian matrix indicate the connectivity and clustering properties of the graph. The smallest eigenvalue (excluding 0) indicates the graph’s algebraic connectivity, with larger values suggesting stronger connectivity. The multiplicity of the eigenvalue 0 represents the number of connected components in the graph.
Eigenvectors: Eigenvectors help in identifying how vertices within the graph are grouped or the position of vertices within the graph’s structure. For example, the eigenvector corresponding to the second smallest eigenvalue (Fiedler value) is known to be useful in dividing the graph into two communities or clusters.
Graph Partitioning: Utilizing the eigenvectors of the Laplacian matrix can effectively partition the graph. This finds natural divisions within the network, applying to community detection or clustering tasks.
Spectral Clustering: Spectral clustering using the eigenvalues and eigenvectors of the Laplacian matrix is a common method for dividing data points on a graph into clusters. This method uses eigenvectors to create a new representation of data points, upon which clustering is performed.

Why number of 0 eigen values correspond to number of connectivity?

Therefore Laplacian matrix definition, it is obvious that

L\mathbf{1} = 0

It means that

L\mathbf{1}=Lv=0v

So, the eigen vector v=1 corresponds to the eigenvalue 0 of L.

On top of that, the number of zero eigenvalues of the Laplacian exactly matches the number of connected components in the corresponding graph.

This means that by performing eigenvalue decomposition on L, we can understand the properties of the graph. Interestingly, it seems that the closer the eigenvalues are to 0, the lower the connectivity of the graph.