Information Technology Reference
In-Depth Information
The final layout emphasizes variation in local density by considering only
deeply embedded edges as expressed by the weights introduced in the next
section.
3 Edge Embeddedness by Accumulating Triadic Effects
Real world networks are often aggregates of different relations, which can hamper
the detection of subgroups or clusters. Our goal is to determine strong embedded
edges, which are likely to be in dense groups, so that we can use them to em-
phasize the inherent structure. The assumption here is that vertices in the same
subgroup of a network are connected stronger with each other than to members
outside of the group.
Satuliri et al. [20] propose to capture the embeddedness of an edge
e
=(
u,v
)
by the Jaccard coecient over
u
's and
v
's neighborhood. Nick et al. [17] suggest
a more general framework, consisting of the following main steps:
1. For each edge, determine its strength
2. For each vertex, rank all its neighbors according to the edge strength
3. For each edge, determine its redundancy
The approach of Satuliri et al. can be seen as using a uniform edge strength for
step one and the Jaccard coecient for the redundancy in step three. Contrary to
this, Nick et al. use the number of triangles an edge is embedded in (Simmelian
strength) for step one and the best prefix Jaccard coecient for step three.
The latter chooses
k
such that the Jaccard coecient of the first top
k
ranked
neighbors of
u
and
v
is maximized. The effect of this ranking measure is that the
highly ranked neighbors have more importance attached, since fewer common
vertices are needed to get a high coecient.
A more intuitive interpretation of this framework is that for an edge
e
=(
u,v
)
the edge strength allows us to determine the most important neighbors of
u
and
v
. If these most important neighbors are
the same
,
e
is strongly embedded;
otherwise
e
is connecting two vertices, which are likely to be in different groups.
We follow the main idea, but propose a differ-
ent edge strength than the number of triangles.
Consider the setting in Fig. 2. Clearly, edge
e
is strongly embedded. Compared to all other
edges it closes many triangles resulting in an
increase of the
group performance
[5] by in-
troducing mediator effects. Similar to this, an
edge (
s, t
) connecting two triangles at
e
intro-
duces additional mediator effects on the trian-
gles, which in turn increases the importance of
e
.Wecalltheseedges
mediator edges
on
e
.
Counting the number of triangles at
e
does not capture the importance of
mediator edges. But since each mediator edge creates two quadrangles at
e
,cf.
dashed-contour in Fig. 2, we can use the number of quadrangles containing
e
s
t
e
u
v
Fig. 2.
Triangles at edge
e
[17,20]
do not capture
mediator edges
(bold), while quadrangles do.
