Information Technology Reference
In-Depth Information
0.9
1.00
0.8
Ⓩ
0.75
Ⓩ
0.7
Ⓩ
Ⓩ
Ⓩ
Ⓩ
Ⓩ
Ⓩ
Ⓩ
Ⓩ
Ⓩ
Ⓩ
Ⓩ
0.50
0.6
Random
Density
Jaccard
Simmelian
Quadrilateral
Ground Truth
Ⓩ
Ⓩ
Random
Density
Jaccard
Simmelian
Quadrilateral
Ⓩ
Ⓩ
Ⓩ
Ⓩ
Ⓩ
0.25
0.5
Ⓩ
Ⓩ
0.4
0.00
100%
75%
50%
25%
100%
75%
50%
25%
remaining edges
remaining edges
(a) layout error
(b) Caltech36
(c) synthetic networks
Fig. 5.
Layout error of different edge embedding methods combined with our UMST
for (b) a real world network and (c) synthetic networks. (a) shows the layout error for
a single point of the line chart in (b).
#homophily edges
#homophily edges + #heterophily edges
homophily(
G
)=
should monotonically increase, while gradually removing edges from the network
according to their weight. Edges for which the class membership (attribute) of
at least one vertex is missing are neglected.
Additionally, we would like to see how well this class membership is reflected
in the layouts. Vertex pairs of the same class should have a small Euclidean
distance, while pairs of different classes should have a large Euclidean distance.
Looking at the curve of the Euclidean distance distribution of the intra-cluster
and inter-cluster vertex pairs in Fig. 5(a), we define the layout error as the
intersection area of these two curves. The layout error can also be interpreted
as the percentage of vertex pairs, where the distinction whether they are in the
same cluster or not cannot clearly be made based on the Euclidean distance.
Since the computation of this quality metric is very time intensive, it was not
feasible to analyze all 100 Facebook networks with it.
4.4 Results and Discussion
An interesting observation from Fig. 3 is that Jaccard and Simmelian perform
very similar for most Facebook networks. Our method (Quadrilateral) clearly
manages to distinguish between the different types of edges better than the
other methods, especially in earlier phases of the sparsification.
For all 100 Facebook networks, the difference in homophily between Simmelian
and Quadrilateral is shown by the length of a vertical segment in Fig. 4. While
both approaches increase the percentage of homophily edges (all segments above
the diagonal dashed line), Quadrilateral clearly performs better, especially for
networks with higher percentage of homophily edges.
Although the homophily of Jaccard and Quadrilateral is nearly the same for
the last but one step of the Caltech network (Fig. 3) the Quadrilateral embedding
