what-when-how
In Depth Tutorials and Information
We can see from Formula (4.1) that the eigenvector
xi
is represented as a column
vector. he row vector (
x
1
u
,
x
2
u
, …,
xnu
) represents the coordinates of node
u
in the
n
-dimensional spectral space. Next, we shall show that only the coordinates of node
u
in the first
k
-dimensional spectral space determine the randomness of
u
where
k
indicates the number of communities within the graph. Hence, we define
α
u
= (
x
1u
,
x
2u
, …,
x
ku
) Î R
1#k
as the spectral coordinate of node
u
in the
k
-dimensional space.
In this section we explore how the spectral coordinate (
α
) of a node point locates
in the projected spectral space. Especially, we show that node points locate along
k
quasi-orthogonal lines when graph
G
contains
k
communities.*
Proposition 1.
For a graph with k communities, the coordinate of node u in
k-dimensionalspace,
α
u
=
(
x
1u
,x
2u
,…,x
ku
)
ÎR
1#k
,denotesthelikelihoodofnodeu's
attachment to these k communities. Node points within one community form a line
thatgoesthroughtheorigininthek-dimensionalspace.Nodesinkcommunitiesformk
quasi-orthogonallinesinthespectralspace
.
Proof. Consider the division of a graph
G
into
k
nonoverlapping communities
G
1
,
G
2
, …,
G
k
. Let
si
= (
s
i1
,
s
i2
, …,
s
in
) be the index vector of community
G
i
, and
s
ij
equals 1 if node
j
belongs to community
G
i
, and it equals 0 otherwise. Note that
s
i
and
s
j
are mutually orthogonal, that is,
s
j
=
0
.
For community
Gi
, we can define its density as
s
T
i
#
of edges in
of nodes in
G
)
:=
i
.
D G
(
i
#
G
i
It can be expressed as
s As
s
T
i
i
D G
(
)
=
i
i
T
s
i
where
A
is the adjacency matrix of graph
G
. he density for this division of the
graph is
k
k
∑
∑
s As
s
i
T
.
(4.2)
=
i
D G
(
)
i
s
T
i
i
=
=
i
1
i
1
he task of our graph partition is to maximize Equation 4.2 subject to
sij
Î {0, 1}
and
s
i
T
j
=
0,
if
i
≠
j
. his optimization problem is NP-complete. However, if we
relax
sij
Î {0, 1} to real space, based on Wielandt's theory [35], we have that the
target function reaches the maximum
Σ
i
k
s
=
1
λ
when taking
si
to be
xi
. Hence we
i
*
Communities are loosely defined as collections of individuals who interact unusually
frequently.
