what-when-how
In Depth Tutorials and Information
In this chapter, we also need to know whether the eigenvalue
μ
2
of the Laplacian
matrix
L
of a particular graph
G
increases or decreases when an edge is relocated.
We derive sufficient conditions on how to adjust
μ
2
of the Laplacian matrix for
two randomization strategies,
RandAdd/Del
and
RandSwitch
. We summarize our
results in the last two rows of Tables 4.2 and 4.3 (the detailed proof can be found
in the Appendix of Reference 40). Note that
μ
2
is the important eigenvalue of the
Laplacian matrix
L
. We use
μ
i
and
�
to denote the
i
-th smallest eigenvalue of
L
and
L
,
respectively, and
u
2
denotes the eigenvector of
μ
2
. Spectrum
y
2
i
is the
i
-th
component of
u
2
.
Based on the derived conditions, we give our spectrum-preserving approach,
which can improve simple edge randomization by considering the change of spec-
trum in the randomization process. Here we can determine which edges we should
add/remove or switch so that we can control the move of target eigenvalues. As a
result, real graph characteristics (or graph utility) are expected to be better pre-
served. Our
SpctrSwitch
algorithm follows.
In Row 2 of the algorithm, we only calculate the first one or two eigenvalues
of the corresponding graph matrices. It is not necessary or desirable to calculate
the entire eigen decomposition. Note that calculation of the eigenvectors of an
n
×
n
matrix takes in general a number of operations
O
(
n
3
). Rows 6 to 11 present
how to switch based on the suicient conditions listed in Table 4.3. he algo-
rithm can be modified to
SpctrAdd/Del
with some minor changes: replacing the
switch process with the
Add/Del
process in Rows 8 and 11; and finally, in Rows
7 and 10, referring to Table 4.2 for the conditions under which the eigenvalues
increase or decrease.
i
Table 4.3
ConditionsonAdjusting
λ
1
and
μ
2
for
Spctr Switch
Condition
Action
(
x
1
t
-
x
1
u
)(
x
1
v
-
x
1
w
) > 0
>
λ
λ
1
1
(
x
1
t
-
x
1
u
)(
x
1
v
-
x
1
w
) < 0, and
λ
<
λ
λ
1
1
y
y
−
−
y
−
−
y
−
λ
>
+
1
t
1
u
1
w
1
v
1
2
y
y
y
y
w
v
t
u
1
1
1
1
(
y
2
t
-
y
2
u
)(
y
2
v
-
y
2
w
) > 0
<
μ
μ
2
2
(
y
2
t
-
y
2
u
)(
y
2
v
-
y
2
w
) < 0,
and
μ
>
μ
μ
2
2
y
−
−
y
y
−
−
y
−
μ
>
t
u
+
2
2
2
w
2
v
u
3
2
y
y
y
y
2
w
2
v
2
t
2
