In graph theory, the Laplace matrix is a matrix that describes the relationships between the nodes and edges of a graph. Among other things, it is used to calculate the number of spanning trees and to estimate the expansiveness of regular graphs. It is a discrete version of the Laplace operator .
Laplace matrices and in particular their eigenvectors belonging to small eigenvalues are used in spectral clustering , a method of cluster analysis .
definition
The Laplace matrix of a graph with the set of nodes and the set of edges is a matrix. It is defined as , where denotes the degree matrix and the adjacency matrix of the graph. So the node and corresponding entry is
L.
{\ displaystyle L}
V
{\ displaystyle V}
E.
{\ displaystyle E}
|
V
|
×
|
V
|
{\ displaystyle | V | \ times | V |}
L.
: =
D.
-
A.
{\ displaystyle L: = DA}
D.
{\ displaystyle D}
A.
{\ displaystyle A}
v
i
{\ displaystyle v_ {i}}
v
j
{\ displaystyle v_ {j}}
L.
i
,
j
: =
{
deg
(
v
i
)
if
i
=
j
-
1
if
i
≠
j
and
v
i
adjacent to
v
j
0
otherwise
{\ displaystyle L_ {i, j}: = {\ begin {cases} \ deg (v_ {i}) & {\ mbox {falls}} \ i = j \\ - 1 & {\ mbox {falls}} \ i \ neq j \ {\ mbox {and}} \ v_ {i} {\ mbox {adjacent to}} v_ {j} \\ 0 & {\ mbox {otherwise}} \ end {cases}}}
In particular, the Laplace matrix is a - regular graph
d
{\ displaystyle d}
L.
=
d
⋅
I.
-
A.
{\ displaystyle L = d \ cdot IA}
with the identity matrix .
I.
{\ displaystyle I}
example
Numbering of the corners
Degree matrix
Adjacency matrix
Laplace matrix
(
2
0
0
0
0
0
0
3
0
0
0
0
0
0
2
0
0
0
0
0
0
3
0
0
0
0
0
0
3
0
0
0
0
0
0
1
)
{\ displaystyle \ left ({\ begin {array} {rrrrrr} 2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 3 & 0 \\ 0 & 0}} \ & 0 & 0 & {1 \\ 0 & 0}} \ & 0 & 0 & {1}
(
0
1
0
0
1
0
1
0
1
0
1
0
0
1
0
1
0
0
0
0
1
0
1
1
1
1
0
1
0
0
0
0
0
1
0
0
)
{\ displaystyle \ left ({\ begin {array} {rrrrrr} 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0}}} \ & 1 & 0 & {
(
2
-
1
0
0
-
1
0
-
1
3
-
1
0
-
1
0
0
-
1
2
-
1
0
0
0
0
-
1
3
-
1
-
1
-
1
-
1
0
-
1
3
0
0
0
0
-
1
0
1
)
{\ displaystyle \ left ({\ begin {array} {rrrrrr} 2 & -1 & 0 & 0 & -1 & 0 \\ - 1 & 3 & -1 & 0 & -1 & 0 \\ 0 & -1 & 2 & -1 & 0 & 0 \\ 0 & 0 & -1 & 3 & -1 & -1 \\ - 1 & -1 & 0 & -1 & 3 & 0 \\ 0 & 0 & 0 & -1 & 0 & 1 \\\ end {array}} \ right)}
Relation to incidence matrix
The Laplace matrix can also be calculated from the incidence matrix . Let be an incidence matrix, then the Laplace matrix is given by
B.
{\ displaystyle B}
|
E.
|
×
|
V
|
{\ displaystyle | E | \ times | V |}
L.
=
B.
⊤
B.
{\ displaystyle L = B ^ {\ top} B}
properties
We denote the eigenvalues of the Laplace matrix, see spectrum (graph theory) .
λ
0
≤
λ
1
≤
⋯
≤
λ
n
-
1
{\ displaystyle \ lambda _ {0} \ leq \ lambda _ {1} \ leq \ cdots \ leq \ lambda _ {n-1}}
L.
{\ displaystyle L}
is symmetrical .
L.
{\ displaystyle L}
is positive-semidefinite , especially for everyone .
λ
i
≥
0
{\ displaystyle \ lambda _ {i} \ geq 0}
i
{\ displaystyle i}
L.
{\ displaystyle L}
is an M-matrix .
The column and row totals are zero. In particular, is with eigenvector .
λ
0
=
0
{\ displaystyle \ lambda _ {0} = 0}
v
0
=
(
1
,
1
,
...
,
1
)
{\ displaystyle \ mathbf {v} _ {0} = (1,1, \ dots, 1)}
The multiplicity of the eigenvalue is the number of connected components of the graph.
0
{\ displaystyle 0}
<img src="https://de.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">