Extracting Communities from Complex Networks by the k-Dense Method
スポンサーリンク
概要
- 論文の詳細を見る
To understand the structural and functional properties of large-scale complex networks, it is crucial to efficiently 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 recently, the k-clique based community extraction method. The k-core method, although computationally efficient, is often not powerful enough for uncovering a detailed community structure and it produces only coarse-grained and loosely connected communities. 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 efficient 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 efficiently as the k-core method, while the qualities of the extracted communities are comparable to those obtained by the k-clique method.
- (社)電子情報通信学会の論文
- 2008-11-01
著者
-
SAITO KAZUMI
NTT Communication Science Laboratories
-
Saito Kazumi
Ntt Communication Science Laboratories Ntt Corporation
-
YAMADA Takeshi
NTT Communication Science Laboratories, NTT Corporation
-
KAZAMA Kazuhiro
NTT Network Innovation Laboratories, NTT Corporation
-
Kazama Kazuhiro
Ntt Network Innovation Laboratories Ntt Corporation
-
Yamada Takeshi
Ntt Communication Science Laboratories Ntt Corporation
関連論文
- SBSOM : Self-Organizing Map for Visualizing Structure in the Time Series of Hot Topics(Text Mining I)
- SBSOM : Self-Organizing Map for Visualizing Structure in the Time Series of Hot Topics(Text Mining I)(Joint Workshop of Vietnamese Society of AI, SIGKBS-JSAI, ICS-IPSJ, and IEICE-SIGAI on Active Mining)
- Extracting Communities from Complex Networks by the k-Dense Method
- Autonomous Development of Relationships among Web Servers for Facilitating Information Utilization( Software Agent and Its Applications)
- Extracting regression rules from neural networks
- Modeling of growing networks with directional attachment and communities