Information Technology Reference
In-Depth Information
(a) drawing, original network
(b) triadic Simmelian backbone [17]
(c) triadic Simmelian backbone
with UMST
(d) quadrilateral Simmelian backbone
with UMST (our approach)
Fig. 1.
Facebook friendships at California Institute of Technology (Caltech36). Vertex
color corresponds to dormitory (gray for missing values), but has not been utilized in
the layout algorithm. The layout in (a) is based on the entire hairball graph, whereas
(b)-(d) use edge embeddedness, which spreads the graph while keeping cohesive groups
together. Embeddedness mapped to edge color; backbone edges dark gray.
This leads to the following requirements on our backbone:
(i) Edges should be favored based on their structural embeddedness only.
(ii) Connectedness has to be maintained.
Two common approaches to simplify a graph
G
=(
V,E,w
) with vertex set
V
,
edge set
E
,andedgeweight
w
:
E
ₒ
R
≥
0
,are
sampling
[2,23] and
thresholding
[1,17,20]. Note that we assume that
w
reflects the embeddedness of an edge and
a higher value corresponds to stronger embeddedness. Although sampling can
be used for sparsification purposes the random selection of edges violates both
of our requirements. In contrast thresholding guarantees that edges are favored
by their weights and consequently their structural properties, as it retains only
the top
k
percent of edges with respect to
w
. Nevertheless, neither nodal nor
network wide thresholding can ensure that the simplified graph stays connected.
