what-when-how
In Depth Tutorials and Information
Result 1.
henonrandomnessofnodeuisthelengthofitsspectralvectorwitheigen-
valuesweightedoncorrespondingdimensions:
∑
1
k
( )
=
λ
=
α
Λ
α
,
R u
x
2
T
(4.3)
i
iu
u
k
u
i
where
Λ
k
=
diag
{
λ
1
,
λ
2
,…,
λ
k
}.
Proof. Let
a
u
denote the
u
-th row of the adjacency matrix
A
. Since
x
i
satisfies
A
x
i
=
λ
i
x
i
and
A
is symmetric,
⎛
a
1
⎞
⎛
x
⎞
i
1
⎜
⎜
⎜
⎜
⎜
⎟
⎟
⎟
⎟
⎟
⎜
⎜
⎜
⎜
⎜
⎟
⎟
⎟
⎟
⎟
=
= λ
.
x
Ax
i
i
i
a
x
⎝
⎠
⎝
⎠
n
in
Hence,
a
u
x
i
=
λ
i
x
iu
, and we have
n
k
k
⎛
⎜
n
⎞
⎟
∑
∑∑
∑ ∑
R u
( )
=
R u v
(
,
)
=
a x x
=
x
a x
uv
iu iv
iu
uv
iv
v
∈
Γ
(
u
)
v
=
1
i
=
1
i
=
1
v
=
1
k
k
∑
∑
=
x a x
=
λ
x
iu
2
=
α α
Λ
.
T
iu u i
i
u
k
i
=
1
i
=
1
We can see that the result is elegant since node nonrandomness is actually deter-
mined by its vector length weighted by eigenvalues of the adjacency matrix.
Using the node nonrandomness measure, we can easily separate singleton
nodes* and noise nodes (with small
R
(
u
) values) from those nodes strongly attached
to some community (with large
R
(
u
) values). We can also identify those nodes
bridging across several groups by examining its relative positions to orthogonal
lines corresponding to different communities.
4.3.2.3 Graph Nonrandomness
RG
and
Relative Nonrandomness
R
G
∗
In our framework, graph nonrandomness
RG