Information Technology Reference
In-Depth Information
This implies that any pair of adjacent nodes in
Q
(2) needs to have more than
or equal to (
k
2) common adjacent nodes. By extending Equation (14.8) for
any
h
and
h
-clique
Q
(
h
) such that 1
−
h<k
, we can define the
h
-level
k
-dense
subnetwork
D
(
k
;
h
)=(
V
D
(
k
;
h
)
,E
D
(
k
;
h
)
) as follows:
≤
∀
Q
(
h
)
⊂
D
(
k
;
h
)
⇒|
F
D
(
k
;
h
)
(
V
Q
(
h
)
)
|≥
k
−
h
(14.9)
By identifying
Q
(1) with a single node,
D
(
k
; 1) is identical to the
k
-core
C
(
k
),
i.e.,
D
(
k
;1) =
C
(
k
). On the other hand, by setting
h
=
k
−
1 we can easily
see that any node
i
in
D
(
k
;
k
−
1) belongs to at least one
k
-clique. This implies
that (
k
−
1)-level
k
-dense
D
(
k
;
k
−
1) is identical to the
k
-clique union
R
(
k
), i.e.,
D
(
k
;
k
1)-level
k
-dense community corresponds
to a union of
k
-clique communities that share at least one node. To summarize,
the
k
-dense together with its higher level extension can be regarded as a general
concept that naturally interpolates between the
k
-core and the
k
-clique union.
A higher-level
k
-dense community is a subnetwork of corresponding lower-level
k
-dense community. Our preliminary experiments show that for many networks,
most of the higher-level
k
-dense communities with
h>
2 are more or less ap-
proximated by the corresponding 2-level
k
-dense communities, while we need
asubstantialamountofcommutationloadforextractinghigherlevel
k
-dense
communities. Therefore, from a viewpoint of the applicability to large-scale net-
works, we should only focus on the 2-level
k
-dense and we refer it simply as
k
-dense.
−
1) =
R
(
k
). Note that a (
k
−
14.2.5
Other Notions of Subnetworks
Distance-based cliques that generalize the notion of a clique, such as an
n
-step
clique
2
,oran
n
-club are widely used in several settings of social network analysis
theory [3]. Here a subnetwork is called an
n-step clique
if and only if the geodesic
distance of any node pair in the original network is less than or equal to
n
, while
a subnetwork is called an
n-club
if and only if the diameter (the maximum
geodesic distance among all node pairs) of the subnetwork is less than or equal
to
n
. Clearly a 1-step clique or 1-club is nothing but a clique, and all nodes
in an
n
-step clique or
n
-club need not be adjacent for
n
2. However, since
many real-world networks have small diameters, it is widely recognized that the
distance is a rather coarse measure to identify meaningful network structures.
A concept called
n-plex
generalizes the notion of a clique in another direc-
tion [3]. A subnetwork
P
(
n
)=(
V
P
(
n
)
,E
P
(
n
)
) is called an
n-plex
if and only if it
satisfies the following condition:
≥
i∈V
P
(
n
)
{|F
P
(
n
)
(
i
)
|≥|V
P
(
n
)
|−n}.
min
(14.10)
2
In order to avoid confusion, we use the term “
n
-step clique” here, although the
same term “
n
-clique” is often used for this generalized clique as well.
