Databases Reference
In-Depth Information
Fig. 24.
Example of clustering. One of the most informative single link candidate is selected from
each cluster. For example,
d
is selected from the cluster
{
d
,
e
}
.
1
(
s
,
t
))
sim
((
s
,
t
)
,
=
t
))
2
.
(9)
n
i
=
1
(
1
+
σ
i
(
s
,
t
)
−σ
i
(
s
,
Note that we added 1 to the denominator to prevent divisions by 0.
Graph Clustering.
The basic intuition behind using clustering for COALA is that
groups of very similar link candidates can be represented by a single link candidate.
Consequently, once a representative of a group has been chosen, all other elements of
the group become less informative. An example that illustrates this intuition is given in
Figure 24. We implemented COALA based on clustering as follows: In each iteration,
we begin by first selecting two sets
S
+
⊆P
S
−
⊆N
that contain the positive resp.
negative link candidates that are most informative for the classifier at hand. Formally,
S
+
fulfills
resp.
∈S
+
∀
S
+
→
∀
x
y
∈P,
y
ifm(
y
)
≤
ifm(
x
)
.
(10)
S
−
. In the following, we will explain the further steps
The analogous equation holds for
S
+
. The same steps are carried out for
S
−
.
of the algorithm for
S
+
by using the similarity func-
tion shown in Equation 9. In the resulting similarity matrix, we set all elements of the
diagonal to 0. Then, for each
x
First, we compute the similarity of all elements of
∈S
+
, we only retain a fixed number
ec
of highest sim-
ilarity values and set all others to 0. The resulting similarity matrix is regarded as the
adjacency matrix of an undirected weighted graph
G
=
,
,
(
V
E
sim
).
G
's set of nodes
V
is equal to
S
+
. The set of edges
E
is a set of 2-sets
19
of link candidates. Finally, the
weighted function is the similarity function
sim
. Note that
ec
is the minimal degree of
nodes in
G
.
In a second step, we use the graph
G
as input for a graph clustering approach. The
resulting clustering is assumed to be a partition
V
of the set
V
of vertices of
G
.The
informativeness of partition
V
i
∈V
is set to max
x
ifm(
x
). The final step of our approach
∈
V
i
19
A
n
-set is a set of magnitude
n
.
