Engineering Math  Quick Reference Home : www.sharetechnote.com 
Graph Theory  Laplacian/Combinatorial Laplacian/Normalized Laplacian
Formal definition of Laplacian is as follows. In a Graph G, Laplacian L is defined as
What is 'di' ? It is the diagonal elelment of 'Degree Matrix'. Actually, Laplacian can be obtained by combining the degree matrix and the adjacency matrix as follows.
Example >
Let's assume that we have a Graph as shown below.
The adjacency matrix of this graph is as follows (try to build this matrix on your own as a practice).
The degree matrix of this graph is as follows (try to build this matrix on your own as a practice).
The Laplacian of this graph calculated from 'DA' become as follows.
In many case, 'Normalized Laplacian' are used. The Normalized Laplacian is defined as follows. (As you see, we divide all the elements of Laplacian in such a way that the diagonal values become '1'. (di is the diagonal values on Laplacian matrix).
Normalized Laplacian given in this example become as follows :
