Information Technology Reference
In-Depth Information
and the weighted degree
d
i
of vertex
u
i
is defined as
d
i
=
∑
j
:
(
i
,
j
)
∈
E
w
ij
,
and the
degree matrix
D
u
=(
d
ij
)
n
×
n
of the graph is a diagonal matrix as
d
i
,
if
i
=
j
,
d
ij
=
0
,
otherwise.
Similarly, we can get the degree matrix
D
v
. The degree matrix of the bipartite
graph
G
=(
U
,
V
,
E
)
is
D
u
0
0
D
v
D
=
,
where the diagonal elements of
D
u
and
D
v
are weighted degree of vertices belonging
to
U
and
V
, and all other elements are 0. The Laplacian matrix of the bipartite graph
G
=(
U
,
V
,
E
)
for data set
A
is defined as
D
u
−
A
L
=
D
−
W
=
.
A
T
D
v
−
The production of spectral clustering is exclusive row and column biclusters.
Therefore, the corresponding subgraphs
H
k
of
G
are disjoint with each other. The
weight of edges between such subgraphs is defined as cut. Without loss of generality,
assume there are two subgraphs
H
1
=(
U
1
,
V
1
,
E
1
)
and
H
2
=(
U
2
,
V
2
,
E
2
)
such that
U
1
∪
U
2
=
U
,
U
1
∩
U
1
=
0
,
V
1
∪
V
2
=
V
,
V
1
∩
V
2
=
0, and
E
i
⊆
E
induced all edges
between
U
i
and
V
i
. Subgraphs
H
1
=(
are called a
partition of
G
. The cut of such partition of bipartite graph is the sum of weights of
edges between
U
1
,
U
1
,
V
1
,
E
1
)
and
H
2
=(
U
2
,
V
2
,
E
2
)
V
2
and
U
2
,
V
1
, i.e.,
∑
cut
(
H
1
,
H
2
)=
w
ij
.
i
∈
U
1
,
j
∈
V
2
,
(
i
,
j
)
∈
E
and
i
∈
U
2
,
j
∈
V
1
,
(
i
,
j
)
∈
E
Obviously, the objective of biclustering is to minimize such intersimilarities be-
tween biclusters (subgraphs). At the same time, the similarities within each bi-
cluster should be maximized. The intrasimilarity of bicluster(subgraph) is defined
as
∑
k
. In order to balance the intersimilarities and intrasimilarities of biclusters,
several different cuts are defined, such as ratio cut [27, 17, 33], normalized cut
[51, 33], minimax cut [60], ICA cut [45]. The most popularly used are ratio cut and
normalized cut.
For a partition
H
1
=(
U
1
,
V
1
,
E
1
)
,
H
2
=(
U
2
,
V
2
,
E
2
)
of the bipartite graph
G
=
(
U
,
V
,
E
)
, the ratio cut is defined as
cut
(
H
1
,
H
2
)
cut
(
H
2
,
H
1
)
+
,
|
U
1
∪
V
1
|
|
U
2
∪
V
2
|
and the normalized cut is defined as
