Extracting Communities from Complex Networks by the k-Dense Method

Access this Article

Search this Article

Author(s)

Abstract

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 <i>k</i>-core decomposition method and, more recently, the <i>k</i>-clique based community extraction method. The <i>k</i>-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 <i>k</i>-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 <i>k</i>-dense, and propose an efficient algorithm for extracting <i>k</i>-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 <i>k</i>-dense method could extract communities almost as efficiently as the <i>k</i>-core method, while the qualities of the extracted communities are comparable to those obtained by the <i>k</i>-clique method.

Journal

  • IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 91(11), 3304-3311, 2008-11-01

    The Institute of Electronics, Information and Communication Engineers

References:  18

Codes

Page Top