what-when-how
In Depth Tutorials and Information
≤
λ
+
ε
≤
λ
λ
(4.6)
+ −
i
j
+ −
i
j
1
i
j n
for
1 Y
i
,
j
,
i
+
j
- 1,
i
+
j
-
n
Y
n
.
Weyl's theorem states that the eigenvalues of a matrix are perfectly conditioned,
that is, no eigenvalue can move more than the range specified by Equation 4.6.
Some graph features (e.g., the number of vertices
n
, the number of edges
m
)
remain unchanged after randomization and are assumed to be available. We also
assume the number of perturbations
k
is available to data miners. he reason is
that
k
denotes the magnitude of perturbation that may be needed to analyze the
perturbed graph by data miners. In this section we present to what extent the
graph spectrum may change with respect to those graph invariants, specifically,
k
and
n
for
RandAdd/Del
, and
k
,
n
, and
d
i
for
RandSwitch
, where
d
i
is the degree
of vertex
i
.
When
k
= 1, we call the perturbation matrix the elementary perturbation matrix
(EPM). Obviously, the perturbation matrix
E
when
k
> 1 is the sum of EPMs along
the perturbation. For
RandAdd/Del
, we have two different cases. One is that we
add the edge (
i
,
p
) and delete an existing edge (
i
,
q
). Specifically,
eip
=
epi
= 1,
and
eiq
=
eqi
= -1, where
eij
denotes the component of
E
. We can derive
ε
1
=
,
ε
n
= −
2,
and
oi
= 0 (2 Y
i
Y
n
- 1). he other case is that we add the edge (
i
,
j
) and
then remove one existing edge (
p
,
q
) where
i
,
j
,
p
,
q
are distinct. Specifically,
eij
=
eji
= 1, and
epq
=
eqp
= -1. In this case, we have
o
1
=
o
2
= 1,
on
=
on
-1
= -1, and
oi
= 0
(3 Y
i
Y
n
- 2). For
RandSwitch
, when we switch one pair of edges, (
t
,
w
), (
u
,
v
) to
(
t
,
v
) and (
u
,
w
),
etw
=
ewt
=
euv
=
evu
= -1, and
etv
=
evt
=
euw
=
ewu
= 1. We can
also derive
o
1
= 2,
on
= -2, and
oi
= 0 (2 Y
i
Y
n
- 1). However, when
k
> 1, it is hard
to derive directly the eigenvalues of
E
based on the released
k
. In the following, we
show our result based on the Gershgorin Circle heorem [18].
heorem 3
:
Gershgorin Circle heorem. For an n
×
n matrix A, deine
R
=
Σ
1,
|
a
| .
heneacheigenvalueofAmustbeinatleastoneofthedisksinthe
n
i
j
=
j
≠
i
ij
complexplane:
{
}
)
=
: −
≤
.
C A
(
z
z
a
R z
i
ii
i
Result 4:
Let
o
1
ɛ
1
≥
ɛ
2
≥
…
≥
ɛ
n
on
be the eigenvalues of E. For all i
(1
≤
i
≤
n
),
we have
ε
≤
λ
−
≤
ε
λ
n
i
1
i
(4.7)
ormoreloosely,
λ
−
≤
E
,
λ
i
i
2
(4.8)
wherefor
Rand Add/Del,
