Information Technology Reference
In-Depth Information
We propose that a subnetwork
D
(
k
)of
G
is called
k-dense
if each pair of
adjacent nodes in
D
(
k
) has more than or equal to (
k
2) common adjacent
nodes in
D
(
k
). More specifically, for a given order
k
,the
k
-dense is a subnetwork
D
(
k
)=(
V
D
(
k
)
,E
D
(
k
)
) consisting of the following node set
V
D
(
k
)
⊂
−
V
G
and link
set
E
D
(
k
)
⊂
E
G
:
V
D
(
k
)
=
e
m
,
(14.5)
e
m
∈E
D
(
k
)
E
D
(
k
)
=
{
e
m
:
|
F
D
(
k
)
(
e
m
)
|≥
k
−
2
}
.
(14.6)
Note that in this definition, the link
e
m
and the set of nodes
{
i, j
}
connected
by
e
m
are identified.
The rationale behind this definition is that when we group two nodes con-
nected with a link together into a same community, we need some solid evidence
or witness to support a strong positive relation between them: the fact that they
are just connected by a single link may not strong enough. The existence of
more common adjacent nodes in the same community suggests stronger positive
relation.
We can easily see that
k
-dense implies
k
-core, i.e.,
D
(
k
)
⊂
C
(
k
). This is
because
|
F
D
(
k
)
(
e
m
)
|≥
k
−
2 implies
e
m
⊂
V
C
(
k
)
.Infact,if
e
m
=
{
i, j
}
and
|
F
D
(
k
)
(
e
m
)
|≥
k
−
2, then the node
i
needs to have more than or equal to
(
k
2) adjacent nodes other than the node
j
. Since the nodes
i
and
j
are
adjacent, we can confirm that
−
1. Again we focus on the sub-
network of maximum size with this property as
D
(
k
), and its connected com-
ponents
D
s
(
k
)(1
|
F
D
(
k
)
(
i
)
|≥
k
−
≤
s
≤
S
D
(
k
)
), each of which is referred to as a
k-dense
community
.
Figure 14.2 shows an example of
k
-dense communities, where the subnetwork
D
1
(3) and
D
2
(3) are both 3-dense communities in which each link has at least
one common adjacent node in
D
1
(3) and
D
2
(3) respectively. Please note that
the
D
2
(3), which was first introduced as 4-core
C
2
(4) in Figure 14.1, is in fact
4-dense, or more accurately, 4-clique. The definition of
k
-clique is described in
the next subsection.
D
1
(3)
D
2
(3)
Fig. 14.2.
An example of
k
-dense communities
