Information Technology Reference
In-Depth Information
14.2.3
The
k
-Clique Community
A subnetwork
Q
(
k
)=(
V
Q
(
k
)
,E
Q
(
k
)
)of
G
consisting of
k
nodes is called
k-clique
if each node pair in
Q
(
k
) is mutually adjacent. Since a
k
-clique is a complete
subnetwork of size
k
,wecaneasilyseethata
k
-clique implies a
k
-dense and
k
-core, i.e.,
Q
(
k
)
⊂
D
(
k
)
⊂
C
(
k
). In contrast, a
k
-core or
k
-dense of size
k
is a
k
-clique, i.e.,
|
V
C
(
k
)
|
=
k
implies
Q
(
k
)=
D
(
k
)=
C
(
k
).
Q
1
(5)
Q
2
(5)
R
1
(5)
Fig. 14.3.
An example of
k
-clique communities
1) nodes. The
k-clique community
proposed by Palla et al. [10] is defined as a union of all
the
k
-cliques that can be reached from each other thorough a series of ad-
jacent
k
-cliques. Hereafter we denote each
k
-clique community as
R
s
(
k
)=
(
V
R
s
(
k
)
,E
R
s
(
k
)
). Note that the
k
-core
C
(
k
)(orthe
k
-dense
D
(
k
)) is the union
of all
k
-core communities (or
k
-dense communities), each of which is also
k
-core
(or
k
-dense) itself. On the other hand, the union of all
k
-clique communities is
not itself a
k
-clique or a
k
-clique community. In this paper, we introduce a new
notion called a
k
-clique union
R
(
k
) in order to directly compare it with
C
(
k
)and
D
(
k
). Namely, a
k
-clique union is defined as a subnetwork
R
(
k
)=(
V
R
(
k
)
,E
R
(
k
)
)
constructed by the following operation:
Two
k
-cliques are called adjacent if they share (
k
−
S
R
(
k
)
S
R
(
k
)
R
(
k
)=(
V
R
s
(
k
)
,
E
R
s
(
k
)
)
.
(14.7)
s
=1
s
=1
Figure 14.3 shows an example of a
k
-clique community, where the subnetwork
Q
1
(5) and
Q
2
(5) are both 5-cliques, which share 4 nodes in common, resulting
in their union
R
(5) being a 5-clique community.
14.2.4
Higher-Level
k
-Dense Community
Because a link
e
m
can be identified as a 2-clique
Q
(2), we can reformulate the def-
inition of the
k
-dense subnetwork
D
(
k
)=(
V
D
(
k
)
,E
D
(
k
)
) given in Equation (14.6)
as follows:
∀
Q
(2)
⊂
D
(
k
)
⇒|
F
D
(
k
)
(
V
Q
(2)
)
|≥
k
−
2
.
(14.8)
