Database Reference
In-Depth Information
identical spectra) must be relatively small. Because of that fact, and because
isomorphic graphs are isospectral, one might expect that classes of isospec-
tral and isomorphic graphs coincide. However, it can be shown that the
class of isospectral graphs is larger [24].
It is easy to verify that by (arbitrary) assignment of
x
i
's in an eigenvec-
tor
x
=[
x
1
,x
2
,...,x
n
]of
A
G
to
n
various vertices in
V
, the components of
x
can be interpreted as positive vertex-weight values (attributes) of the cor-
responding vertices in the digraph
G
. This property is extremely useful in
finding connectivity components of
, and in various clustering, coarsening,
or graph condensing implementations [28].
A different approach to graph spectra for undirected graphs [25,29,30]
investigates the eigenvalues of the
Laplace matrix
L
G
=
D
G
−
G
A
G
,wherethe
{
v∈V
w
E
degree matrix
D
G
of graph
G
is defined as
D
G
=diag
(
u, v
)
|u ∈
V
G
}
. Note that in the unweighted case, diagonal elements of
D
G
are sim-
ply the vertex degrees of indexed vertices
. It follows that the Laplacian
spectrum is always nonnegative, and that the number of zero eigenvalues
of
L
G
equals the number of connectivity components of
V
G
.Inthecaseof
(
A
G
+
A
G
digraphs, the Laplacian is defined as
L
G
=
D
G
−
)(inorderto
R
+
). The second smallest eigenvalue (called the
ensure that
σ
(
L
G
)
⊆{
0
}∪
algebraic connectivity
of
) provides graph connectivity information and
is always smaller or equal to the vertex connectivity of
G
[30]. Laplacian
spectra of graphs have many applications in graph partitions, isoperimetric
problems, semidefinite programming, random walks on graphs, and infinite
graphs [25,29].
The relationship between graph spectra and graph distance measures
can be established using an eigenvalue interpretation [27]. Consider the
weighted graph matching problem for two graphs
G
G
=(
V
G
,E
G
)and
H
=
w
E
w
E
(
V
H
,E
H
), where
|V
G
|
=
|V
H
|
=
n
, with positive edge-weights
and
,
which is defined as finding a one-to-one function Φ :
V
G
→ V
H
such that
the
graph distance function
:
dist(Φ) =
u∈V
G
,v∈V
H
w
E
(
))
2
− w
E
(Φ(
u, v
)
u
)
,
Φ(
v
(3.1)
is minimal. This is equivalent to finding a permutation matrix
P
that min-
imises
A
H
||
2
,where
A
G
and
A
H
are the (weighted)
adjacency matrices of the two graphs, and
PA
G
P
T
−
J
(
P
)=
||
is the ordinary Euclidean
matrix norm. Notice that this graph matching problem is computationally
expensive because it is a combinatorial optimisation problem.
·
