下面是維基百科上的描述：
Jump to search
In the mathematical field of graph theory, the Laplacian matrix, sometimes called admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. The Laplacian matrix can be used to find many useful properties of a graph. Together with Kirchhoff's theorem, it can be used to calculate the number of spanning trees for a given graph. The sparsest cut of a graph can be approximated through the second smallest eigenvalue of its Laplacian by Cheeger's inequality. It can also be used to construct low dimensional embeddings, which can be useful for a variety of machine learning applications.
大意是說(shuō)：在圖算法領(lǐng)域蚊锹，Laplacian matrix 有時(shí)被稱為 admittance matrix, Kirchhoff matrix 或者 discrete Laplacian瞳筏，它是 graph 的一種矩陣表示。Laplacian matrix 常常被用來(lái)尋找一些有用的圖(graph)屬性牡昆。結(jié)合基爾霍夫積分定理(Kirchhoff's theorem)姚炕，它常常被用來(lái)計(jì)算一個(gè)給定圖的生成樹(shù)(spanning trees) 的數(shù)目。圖的 sparsest cut 可以通過(guò) Cheeger's inequality 的拉普拉斯矩陣的第二小的特征值來(lái)近似丢烘。
Laplacian matrix for simple graphs
給定的一個(gè)有 個(gè)節(jié)點(diǎn)的簡(jiǎn)單圖(simple graph) , Laplacian matrix
被定義為：
這里 是一個(gè) 度矩陣(degree matrix),
是一個(gè)鄰接矩陣(adjacency matrix). 由于
是一個(gè)簡(jiǎn)單圖柱宦，所以，
中的元素僅僅可能是
和
播瞳，且其對(duì)角元素全為
. 對(duì)于 有向圖(directed graphs), 將會(huì)使用 indegree 和 outdegree . 這樣掸刊，
中的每個(gè)元素是
表示節(jié)點(diǎn)
的度。
Symmetric normalized Laplacian
拉普拉斯矩陣的對(duì)稱標(biāo)準(zhǔn)化：
Random walk normalized Laplacian
random-walk normalized Laplacian matrix :
更多參考 : Laplacian matrix
