Detect overlapping and hierarchical community structure in networks

被引：535

作者：

Shen, Huawei ^{[1
,2
]}

Cheng, Xueqi ^{[1
]}

Cai, Kai ^{[1
]}

Hu, Mao-Bin ^{[3
]}

机构：

[1] Chinese Acad Sci, Comp Technol Inst, Beijing 100190, Peoples R China

[2] Chinese Acad Sci, Grad Univ, Beijing 100049, Peoples R China

[3] Univ Sci & Technol China, Sch Engn Sci, Hefei 230026, Peoples R China

来源：

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS | 2009年 / 388卷 / 08期

基金：

中国国家自然科学基金;

关键词：

Community detection; EAGLE; Modularity; Overlapping & hierarchical community; Maximal clique; COMPLEX; ORGANIZATION; MODULARITY; RESOLUTION;

D O I：

10.1016/j.physa.2008.12.021

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

Clustering and community structure is crucial for many network systems and the related dynamic processes. It has been shown that communities are usually overlapping and hierarchical. However, previous methods investigate these two properties of community structure separately. This paper proposes an algorithm (EAGLE) to detect both the overlapping and hierarchical properties of complex community structure together. This algorithm deals with the set of maximal cliques and adopts an agglomerative framework. The quality function of modularity is extended to evaluate the goodness of a cover. The examples of application to real world networks give excellent results. (c) 2008 Elsevier B.V. All rights reserved.

引用

页码：1706 / 1712

页数：7

共 24 条

[1] Statistical mechanics of complex networks [J].

Albert, R ;

Barabási, AL .

REVIEWS OF MODERN PHYSICS, 2002, 74 (01) :47-97

[2]

[Anonymous], ARXIVCS0608050

[3] FINDING ALL CLIQUES OF AN UNDIRECTED GRAPH [H] [J].

BRON, C ;

KERBOSCH, J .

COMMUNICATIONS OF THE ACM, 1973, 16 (09) :575-577

[4]

Clauset A, 2004, PHYS REV E, V70, DOI 10.1103/PhysRevE.70.066111

[5] Comparing community structure identification -: art. no. P09008 [J].

Danon, L ;

Díaz-Guilera, A ;

Duch, J ;

Arenas, A .

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2005, :219-228

[6] Community detection in complex networks using extremal optimization [J].

Duch, J ;

Arenas, A .

PHYSICAL REVIEW E, 2005, 72 (02)

[7] Self-organization and identification of web communities [J].

Flake, GW ;

Lawrence, S ;

Giles, CL ;

Coetzee, FM .

COMPUTER, 2002, 35 (03) :66-+

[8] Resolution limit in community detection [J].

Fortunato, Santo ;

Barthelemy, Marc .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2007, 104 (01) :36-41

[9] Community structure in social and biological networks [J].

Girvan, M ;

Newman, MEJ .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2002, 99 (12) :7821-7826

[10] Functional cartography of complex metabolic networks [J].

Guimerà, R ;

Amaral, LAN .

NATURE, 2005, 433 (7028) :895-900

← 1 2 3 →