Information Technology Reference
In-Depth Information
Jaccard
Simmelian
Quadrilateral
Ⓩ
Pepperdine86
Rice31
Smith60
Vassar85
0.9
Ⓩ Ⓩ
Ⓩ
Ⓩ
0.90
Ⓩ
Ⓩ
Ⓩ
Ⓩ
0.77
Ⓩ
0.9
Ⓩ
Ⓩ
Ⓩ
0.89
Ⓩ
Ⓩ
Ⓩ
0.8
Ⓩ
Ⓩ
Ⓩ
Ⓩ
0.75
Ⓩ
Ⓩ
Ⓩ
Ⓩ
Ⓩ Ⓩ
Ⓩ
Ⓩ Ⓩ
Ⓩ
0.8
Ⓩ
Ⓩ
0.88
Ⓩ
0.73
Ⓩ
Ⓩ
Ⓩ
Ⓩ
Ⓩ
0.7
Ⓩ
0.87
0.71
0.7
Ⓩ
Ⓩ
0.86
100%
75%
50%
25%
100%
75%
50%
25%
100%
75%
50%
25%
100%
75%
50%
25%
remaining edges
Fig. 6.
Layout error of Facebook networks w.r.t. the dormitory attribute. While im-
provement is not clear for Pepperdine86 and Vassar85, the layout is improved a lot for
the networks with high homophily (Rice31 and Smith60).
creates the superior layout (Fig. 5). Furthermore, for the synthetic networks,
Quadrilateral comes very close to the ground truth (Fig. 5).
Figure 6 shows the layout error for four Facebook networks and the three best
performing edge metrics (according to homophily). The layout clearly improves
for the Rice and Smith network, but not much for the other two. One possible
explanation for this could be that the dormitory attribute is not the explanatory
variable for the formation of social relations in these two networks.
The effectiveness of our layout quality metric can also be verified, by looking at
the final drawings in Fig. 1(c) and 1(d). In the latter many clusters, as light green
and light blue, are more clearly visible. For the synthetic networks our method
comes also very close to the ground truth, in terms of layout error (Fig. 5(c)).
Again, the drawings of a synthetic network (Fig. 7) support this conclusion.
5Con lu on
We proposed a sparsification approach to draw hairball graphs as encountered in
online social networks. It is based on the idea that pairwise distances (the “degrees
of separation”) need to be increased without disrupting tightly-knit groups. The
deeply embedded edges such groups are made of are identified using a suitably
modified Simmelian backbone [17], and overall layout organization is stabilized
by maintaining connectedness via the union of all maximum spanning trees.
An evaluation with empirical and generated networks showed that our novel
metric manages to reveal relations deeply embedded in latent primary groups.
In the resulting drawings such groups are separated from each other but still
positioned in their global context. On the Facebook100 dataset, average distances
increased from about 3 in the original friendship networks to about 14 in the
backbone, thus easing the layout task for force-directed algorithms.
Our proposed edge embeddedness metric proved to be more effective than
previous approaches with respect to improving layout quality by way of ampli-
fying homophily. It is thus likely to be useful as a preprocessing step for graph
clustering algorithms as well.
