Information Technology Reference
In-Depth Information
14
The
k
-Dense Method to Extract Communities
from Complex Networks
Kazumi Saito
1
,
, Takeshi Yamada
2
, and Kazuhiro Kazama
3
1
School of Administration and Informatics, University of Shizuoka
52-1 Yada, Suruga, Shizuoka, Shizuoka 422-8526 Japan
k-saito@u-shizuoka-ken.ac.jp
2
NTT Communication Science Laboratories, NTT Corporation
2-4 Hikaridai, Seika, Soraku, Kyoto 619-0237 Japan
yamada@cslab.kecl.ntt.co.jp
3
NTT Network Innovation Laboratories, NTT Corporation
3-9-11 Midori-cho, Musashino, Tokyo 180-8585 Japan
kazama@ingrid.org
Abstract.
To understand the structural and functional properties of large-scale
complex networks, it is crucial to eciently extract a set of cohesive subnetworks as
communities. There have been proposed several such community extraction methods
in the literature, including the classical
k
-core decomposition method and, more re-
cently, the
k
-clique based community extraction method. The
k
-core method, although
computationally ecient, is often not powerful enough for uncovering a detailed com-
munity structure and it only discovers coarse-grained and loosely connected commu-
nities. The
k
-clique method, on the other hand, can extract fine-grained and tightly
connected communities but requires a substantial amount of computational load for
large-scale complex networks. In this paper, we present a new notion of a subnetwork
called
k
-dense, and propose an ecient algorithm for extracting
k
-dense communities.
We applied our method to the three different types of networks assembled from real
data, namely, from blog trackbacks, word associations and Wikipedia references, and
demonstrated that the
k
-dense method could extract communities almost as eciently
as the
k
-core method, while the qualities of the extracted communities are comparable
to those obtained by the
k
-clique method.
14.1
Introduction
In many scientific and engineering domains, complicated relational data struc-
tures are frequently represented by networks or, equivalently, graphs. For exam-
ple, WWW (World Wide Web) sites are often represented by
hyperlink networks
,
with pages as nodes and hyperlinks between pages as edges, the interactions be-
tween genes, proteins, metabolites and other small molecules in an organism are
represented by
gene regulatory networks
, and the relationships between people
and other social entities are characterized by
social networks
. Extracting a set of
This work has been done while the first author was with NTT Communication
Science Laboratories.