Information Technology Reference
In-Depth Information
The set of the eigenvalues of a matrix is defined to its spectrum. It is easily
proved that the spectrum of the Laplace matrix,
M
, has some properties as
follows:
(i) All spectra of
M
are non-negative.
(ii) 0 is an element of spectrum set of
M
.
(iii) The algebraic multiplicity
q
of 0 is the number of well-defined communities
of the network.
In fact, if the network is full-connected, the algebraic multiplicity of eigenvalue
0 is 1. For example, the spectra of the Laplace matrix of the network determined
by Figure 13.1 are listed as Table 13.1.
Table 13.1.
The spectral decomposition of the Laplace Matrix determined by Figure
13.1. It is obvious in a complex network that the number of nodes equals to the number
of spectra of the corresponding Laplace matrix. From this table, we can find that the
smallest eigenvalue is zero, and the fourth smallest eigenvalue (1.1286) obviously has a
great gap with the previous three eigenvalues. It implies that there are three well-defined
communities in the network, which accords with the result shown in Figure 13.1.
Order
Eigenvalues
1-6
0.0
0.3553
0.4762
1.1286
1.8912
2.2505
7-12
2.7901
3.4170
3.6729
4.0925
4.5766
4.8204
13-18 5.0000
5.0648
5.2332
5.8186
6.6236
6.7886
As mentioned above, the number of eigenvalue 0 is 1 indeed when the network
is full-connected. However, in a network composed by some large components
adding to a few edges between these components, the Laplace matrix has also a
certain number of eigenvalues very closing to zero, and the remaining eigenvalues
have a gap away from zero remarkably. So we can believe that these near-zero
eigenvalue is the dimension of zero eigenvalue.
Suppose that the number of communities is
q
if there are
q
eigenvalues very
closing or equaling to zero. Let
λ
i
(
i
=1
,
2
,...,n
)bethe
i
th smallest eigenvalue
of the Laplace matrix and
ξ
i
be the corresponding eigenvector. Hence, we have
λ
1
(= 0)
≤
λ
1
≤···≤
λ
q−
1
λ
q
≤
λ
q
+1
≤ ···≤
λ
n
.
(13.11)
Since
q
approximately equals to the algebraic multiplicity of zero, it is very
important that selecting an appropriate value of
q
according to the distributed
characteristic of eigenvalues of the Laplace matrix. We select the largest value
of
q
satisfying the following conditions as the appropriate value
q
∗
:
β
(
λ
q
−
λ
q−
1
)
<λ
q
+1
−
λ
q
,
β
=3 and
λ
q
<
1
.
(13.12)
The former term of Equation (13.12) is used to measure the gap between the
whole eigenvalues, and the latter is used to ensure that the selected eigenvalue
closes to zero. And the value
β
measures the gap between all eigenvalues. A large
