what-when-how
In Depth Tutorials and Information
to derive edge nonrandomness, node nonrandomness, and the overall graph non-
randomness from graph spectrum. In Section 4.4 we show how randomization
affects spectral characteristics, and present our spectrum-preserving edge-random-
ization approach. We offer our concluding remarks and discuss future work in
Section 4.5.
4.2 SpectralversusRealCharacteristics
A network or graph,
G
(
V
,
E
), is a set of
n
nodes,
V
, connected by a set of
m
links,
E
. he network considered here is binary, symmetric, connected, and without self-
loops. Let
A
= (
a
ij
)
n#n
be its adjacency matrix,
a
ij
= 1 if node
i
and
j
are connected,
and
a
ij
= 0 otherwise. Associated with
A
is the degree distribution
D
n#n
, a diagonal
matrix with row-sums of
A
along the diagonal, and 0's elsewhere. Recall that the
degree of a node in a network is the number of edges connected to that node.
Let
λ
i
be the eigenvalues of
A,
and
x
i
the corresponding eigenvectors, and
λ
i
∈{λ
1
λ
2
…
λ
n
}. he spectral decomposition of
A
is
A
= Σ λ
x x
.
We call
λ
i
the
index of
G
, and call
x
1
= (
x
11
, …,
x
1
n
)
T
the principal eigenvector of the graph
G
where
x
1
i
is the
i
-th component of the principal eigenvector.
Another matrix related to
A
is the Laplacian matrix defined as
L
=
D
-
A
.*
Similarly, let
μi
be the eigenvalues of
L,
and
u
i
the corresponding eigenvectors. We
have 0 =
μ
1
Y
μ
2
Y … Y
μn
Y
n
. Since the degree
Dii
=
Σ
jAij
, all rows and columns of
the Laplacian sum to zero. Hence, there exists one eigenvalue zero with eigenvector
1
= (1, 1, …, 1).
μ
2
is an important eigenvalue of the Laplacian matrix and can be
used to show how good the communities separate, with smaller values correspond-
ing to better community structures. Let
u
2
= (
y
21
, … ,
y
2n
)
T
where
y
2
i
is the
i
-th
component of the eigenvector
u
2
.
To understand and utilize the information in a network, researches have devel-
oped various measures to indicate the structure and characteristics of the network
from different perspectives [9]. In this chapter, we use four real-space characteristics
of a graph. he irst one is the harmonic mean of the shortest distance,
h
, which is
defined in Reference 25 as
h
i
T
i
i
i
1
Σ
he inverse of the harmonic mean
of the shortest distance, also known as the global efficiency, varies between 0 and 1,
with
h
-1
= 0 when all vertices are isolated, and
h
-1
= 1 when the graph is complete.
he second measure is the modularity measure,
Q
, which indicates the good-
ness of the community structure [9]. It is defined as the fraction of all edges that
lie within communities minus the expected value of the same quantity in a graph
in which the vertices have the same degrees but the edges are placed at random
without regard for the communities. A value
Q
= 0 indicates that the community
structure is no stronger than would be expected by random chance, and values
other than zero represent deviations from randomness.
=
{
1
}
−
.
i
≠
j
d
ij
n n
(
−
1
)
*
he third matrix is the normal matrix defined as N=D
-1/2
AD
-1/2
.
