Information Technology Reference
In-Depth Information
cohesive subnetworks as communities from those large-scale complex networks
plays an important role to understand their basic structures and functions [12],
and it hopefully inspires researchers to discover new knowledge and insights
underlying those complex networks.
For this task, two types of approaches have been studied extensively by many
researchers [5, 7, 9, 10, 14, 15]. One approach is based on
clustering
techniques
that divide all nodes of a network into several communities [5, 7, 15]. Another
approach is based on
core decomposition
techniques that extract only certain
cohesive portions as communities from a given network; thus the union of ex-
tracted communities is not necessarily equal to the original network [9, 10, 14].
The former approach is suitable for understanding the entire structure of a rela-
tively small network by regarding all nodes as equally important, while the latter
can be used for finding the major building blocks of a relatively large network.
In this paper, we focus on the core decomposition approach that extracts
certain cohesive portions as communities from a large-scale network. For this
task, we can employ the classical
k-core decomposition
method, or simply, the
k-core method
[14], or the recently proposed method called CFinder [10] that
extracts a set of
k
-clique communities (therefore for simplicity, we call it the
k-
clique method
in this paper). However, the
k
-core method is usually not powerful
enough for uncovering the detailed community structure although it is compu-
tationally quite ecient, while the
k
-clique method often requires a substantial
amount of computational load for large-scale networks.
In this paper, we present a new concept of subnetwork called
k
-dense, and pro-
pose an ecient algorithm for extracting
k
-dense communities. In Section 14.2,
we present the notion of
k
-dense and
k
-dense communities as well as we review
the notions of
k
-core and
k
-clique communities. We also describe an ecient al-
gorithm for extracting
k
-dense communities. In Section 14.3, we first explain the
three types of networks used in our experiments, and then we describe criteria
for evaluating extracted communities. We then report our experimental results.
In Section 14.4, we discuss some related work and future directions.
Extracting
k
-Dense Communities
14.2
In this section, we present a new notion of a subnetwork called
k
-dense as well
as we review the notions of
k
-core and
k
-clique communities. We also describe
an ecient algorithm for extracting
k
-dense communities.
14.2.1
The
k
-Core Community
Foragivennetwork(orequivalentlygraph)
G
=(
V
G
,E
G
), let
V
G
=
{
1
,
···
,N
}
be a set of nodes (or vertices) and
E
G
=
{
e
1
,
···
,e
M
}
a set of links (or edges),
where
e
m
=
{
i, j
}⊂
V
G
and
i
=
j
, meaning we focus on undirected networks
without self-links.
Now for a given node
i
in the network
G
,wedenote
F
G
(
i
)asasetof
adjacent
nodes
of
i
as follows:
