Information Technology Reference
In-Depth Information
F
G
(
i
)=
{
j
:
{
i, j
}∈
E
G
}
.
(14.1)
A subnetwork
C
(
k
)of
G
is called
k-core
if each node in
C
(
k
) has more than
or equal to (
k −
1) adjacent nodes in
C
(
k
)
1
. More specifically, for a given order
k
,the
k
-core is a subnetwork
C
(
k
)=(
V
C
(
k
)
,E
C
(
k
)
) consisting of the following
node set
V
C
(
k
)
⊂ V
G
and link set
V
C
(
k
)
⊂ V
G
:
V
C
(
k
)
=
{
i
:
|
F
C
(
k
)
(
i
)
|≥
k
−
1
}
,
(14.2)
E
C
(
k
)
=
{
e
m
:
e
m
⊂
V
C
(
k
)
}
.
(14.3)
Here
denotes the number of elements in the set
A
. Hereafter we focus on
the subnetwork of maximum size with this property as
C
(
k
), and its connected
components
C
s
(
k
)(1
|
A
|
S
C
(
k
)
), each of which is referred to as a
k-core
community
.Here
S
C
(
k
)
denotes the number of communities (or connected com-
ponents) in
C
(
k
).
Figure 14.1 shows an example of
k
-core communities, where the subnetwork
C
1
(3) in the outer box is a 3-core community in which each node has at least
two adjacent nodes in
C
1
(3), and
C
1
(4) and
C
2
(4) in the inner boxes are both
4-core communities.
≤
s
≤
C
1
(4)
C
2
(4)
C
1
(3)
Fig. 14.1.
An example of
k
-core communities
14.2.2
The
k
-Dense Community
For a given set of nodes
V
V
G
,wedenoteasetof
common adjacent nodes
F
G
(
V
)of
V
that is a natural extension of
F
G
(
i
) in Equation 14.1 as follows:
F
G
(
V
)=
i∈V
⊂
F
G
(
i
)
.
(14.4)
1
Our definition of
k
-core is, in fact, (
k−
1)-core in the conventional definition. We use
this definition for compatibility with the other core concepts.