Information Technology Reference
In-Depth Information
which can be cast into the matrix form P = WP by dening an evolution matrix
W such that
N
min
X
W
i;j
=
j;i
i;j
i;j
:
(6.3)
j=1
In graph theory literature L =W is often referred to as the Laplacian matrix. The
solutions of the master equation can be straightforwardly derived by diagonalizing
the evolution W; unfortunately, the latter operation is often computationally quite
expensive. One specic eigenstate can nonetheless be easily computed without need
of any diagonalization: the kernel P
0
which corresponds to the stationary condition
on the graph ( P
0
= 0). By setting the left hand side of equation (6.2) equal to 0
one nds that the components of P
0
are:
e
V
i
k
B
T
P
0;i
=
;
(6.4)
Q
N
0
k=1
!
(k)
i
P
i
P
0;i
= 1. Note that the station-
ary probability only depends on minima and any information about the saddles is
lost. Actually the P
0;i
's correspond to the basin occupation probabilities that one
would obtain by approximating the potential at the second order in the minima and
by computing the corresponding partition function. A detailed balance condition
P
0;i
i;j
= P
0;j
j;i
holds for every connected pair i;j.
Connectivity graphs are weighted directed graphs, each connection having a
dierent weight according to the crossing direction. Simpler descriptions might
nonetheless prove useful as well. By forgetting the dynamical weights on the con-
nections one can dene two matrices
discrete
and W
discrete
that share the same
relationship as and W previously dened and such that the i;jth element of
discrete
is one if the two minima are connected and 0 otherwise. The discrete Lapla-
cian matrix L
discrete
=W
discrete
is of fundamental interest because the power{law
behavior of the low frequency part of its spectral density allows to dene the spec-
tral dimension of the graph, a generalization of the Euclidean dimension for graphs
that are not dened on a regular lattice (see Sec. 6.2.2.1).
where is a normalization constant such that
6.2.1. Renormalization of the graph
As stated above, the most dynamically sensible denition of connectivity graph is
that of a graph whose nodes correspond to metastable states of the system. Thus
the graphs where each node corresponds to a minimum of the potential energy can
be considered a good approximation of the connectivity graph only in the zero tem-
perature limit. Actually, as temperature increases, regions of phase space previously
corresponding to dierent metastable states might fuse in a unique metastable state
because the energy barrier that divides them has become dynamically negligible. At
realistic temperatures real metastable states consist in conglomerates of basins of
