Database Reference
In-Depth Information
the same edge [23]. Edges in
G
can be
directed
. In this case edge (
u, v
)
∈ E
originates at node
.
Objects such as vertices or edges (or their combinations) associated with
a graph are referred to as
elements
of the graph. A
weight
is a function whose
domain is a set of graph elements in
u ∈ V
and terminates at node
v ∈ V
. The domain can be restricted to that
of edge or vertex elements only, where the function is referred to as
edge-
weight
or
vertex-weight
respectively. A weight whose domain is all vertices
and edges is called
total
.
Values
of weight assigned to elements in
G
may
be numerical (e.g. the amount of trac in a computer network as values of
edge-weight), or symbolic (e.g. node identifiers as values of vertex-weight).
The set of possible values in the range of the weight function are called
attributes
. A unique labeling is a one-to-one weight, for a vertex-weight
this serves to uniquely identify vertices of a graph. A graph with a unique
labeling is called a
labeled
graph.
The graph
G
G
=(
V,E,w
V
,w
E
) is vertex-labeled with weight
w
V
:
V → L
V
assigning vertex identifier attributes
L
V
to individual vertices,
where the value of an assigned vertex-weight is
w
V
(
u
)forvertex
u
.Fur-
thermore,
since the graphs in our applica-
tion possess unique vertex-labelings. Edges are also weighted with weight
w
E
:
w
V
(
u
)
=
w
V
(
v
)
, ∀u, v ∈ V, uv
E → R
+
. The notation
w
E
is used to indicate that edge weight
w
E
belongs to graph
G
. The number of vertices in
G
=(
V, E
) is denoted by
|V |
, and likewise the number of edges is denoted by
|E|
.
3. Analysis of Graph Spectra
One of the known approaches to the measurement of change in a time
series of graphs is through the analysis of graph spectra. Algebraic aspects
of spectral graph theory are useful in the analysis of graphs [24-27]. There
are several ways of associating matrix spectra (sets of all eigenvalues) with
a given weighted graph
. The most obvious way is to investigate the
structure of a finite digraph
G
by analyzing the spectrum of its adjacency
matrix
A
G
. Note that
A
G
is not a symmetric matrix for directed graphs
because weight may not be a symmetric function.
Foragivenorderingofthesetof
G
n
vertices
V
in a graph
G
=(
V, E
),
one can investigate the
spectrum
σ
(
G
)=
{λ
1
,λ
2
,...,λ
n
}
,where
λ
i
are the
eigenvalues of the weighted adjacency matrix
A
G
. Obviously,
σ
(
G
)does
not depend on the ordering of
. Also, the matrix spectrum does not
change under any nonsingular transformation. Since the adjacency matrices
have nonnegative entries, the class of all isospectral graphs (graphs having
V
