Information Technology Reference
In-Depth Information
to capture this mediator effect. While there can be additional quadrangles at
e
,
they will be counted only once from
e
's perspective, which makes their influence
rather low. Furthermore, counting the two different types of quadrangles at
e
would be too time consuming and therefore we will not distinguish between
them.
Using the absolute number of quadrangles poses diculties, when the network
contains subgroups of different densities. Hence, we normalize this absolute value
by putting it into relation to all edges at vertex
u
and
v
.Let
q
(
u,v
)bethe
number of quadrangles containing edge (
u,v
)
∈
E
. We define the
quadrilateral
edge embeddedness as
q
(
u,v
)
q
(
u
)
Q
(
u,v
)=
q
(
v
)
,
·
where
q
(
v
)=
w∈N
(
v
)
q
(
v,w
), for
v
V
,and
N
(
v
) the neighborhood of
v
.We
use the geometric mean over the arithmetic mean, since it takes the dependency
of two variables into stronger consideration. Note that edge-metrics using quad-
rangles have already been proposed by Auber et al. [1] and Radicchi et al. [19],
but are different from our method as they focus on density. For a comparison of
different edge metrics we refer the reader to Melancon and Sallaberry [16].
∈
Computation and Time Complexity
The quadrangles of a graph
G
can be listed in
O
(
mʱ
(
G
)) [6], where
m
is the
number of edges and
ʱ
(
G
), the
arboricity
of
G
, is the minimum number of edge-
disjoint forests necessary to cover all edges of
G
. While the arboricity can be as
large as
√
m
, it is bounded from above by the
h
-index of a graph which in turn
is found to be very small in social networks [8]. Together with the normalization,
the computation of the edge strengths takes
O
(
mʱ
(
G
)) time.
Neighbors can be ranked in
O
(
m
log
(
G
)) time and redundancy can be com-
puted in
(
G
)isthemaximumvertexdegree. For example,
the overall backbone computation took 0
.
2s on a network with 762 vertices
and 16k edges (Caltech65) and 2
.
3s on a network with 2970 vertices and 100k
edges (Smith60) with our Java 7 implementation and an Intel Core i7-2600K
CPU@3.40GHz. The approach thus scales to large networks and we turn to the
evaluation of its effectiveness in the next section.
O
(
m
(
G
)), where
4 Evaluating Methods for Edge Embeddedness
In this section we introduce the dataset and a graph model, from which we gener-
ate artificial hairball graphs. Then we explain our output quality indicators and
the different edge embeddedness methods. For each graph and edge embedded-
ness method, we iteratively increase the sparsification ratio by 10% and compute
the corresponding backbone. Layouts are computed using stress majorization [9]
initialized by PivotMDS [3] as suggested in [4].
