Community Structures of Networks

被引：9

作者：

Chen, William Y. C. ^{[1
]}

Dress, Andreas W. M. ^{[2
,3
]}

Yu, Winking Q. ^{[1
]}

机构：

[1] Nankai Univ, Ctr Combinator, LPMC, Tianjin 300071, Peoples R China

[2] Chinese Acad Sci, CAS MPG Partner Inst Computat Biol, Shanghai Inst Biol Sci, Shanghai 200031, Peoples R China

[3] Max Planck Inst Math Nat Wissensch, D-04103 Leipzig, Germany

来源：

MATHEMATICS IN COMPUTER SCIENCE | 2008年 / 1卷 / 03期

基金：

美国国家科学基金会;

关键词：

Networks; graphs; community structures; clique partitioning problem; graph partitioning problem; linear programming; integer linear programming; food webs; Zachary's karate club;

D O I：

10.1007/s11786-007-0035-1

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We present an approach to studying the community structures of networks by using linear programming (LP). Starting with a network in terms of (a) a collection of nodes and (b) a collection of edges connecting some of these nodes, we use a new LP-based method for simultaneously (i) finding, at minimal cost, a second edge set by deleting existing and inserting additional edges so that the network becomes a disjoint union of cliques and (ii) appropriately calibrating the costs for doing so. We provide examples that suggest that, in practice, this approach provides a surprisingly good strategy for detecting community structures in given networks.

引用

页码：441 / 457

页数：17

共 33 条

[1] Internet -: Diameter of the World-Wide Web [J].

Albert, R ;

Jeong, H ;

Barabási, AL .

NATURE, 1999, 401 (6749) :130-131

[2] Classes of small-world networks [J].

Amaral, LAN ;

Scala, A ;

Barthélémy, M ;

Stanley, HE .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2000, 97 (21) :11149-11152

[3] Local method for detecting communities [J].

Bagrow, JP ;

Bollt, EM .

PHYSICAL REVIEW E, 2005, 72 (04)

[4] THE SEASONAL DYNAMICS OF THE CHESAPEAKE BAY ECOSYSTEM [J].

BAIRD, D ;

ULANOWICZ, RE .

ECOLOGICAL MONOGRAPHS, 1989, 59 (04) :329-364

[5] Emergence of scaling in random networks [J].

Barabási, AL ;

Albert, R .

SCIENCE, 1999, 286 (5439) :509-512

[6]

Bondavalli C., 2006, E COMMUNICATION

[7]

Borgwardt K.-H., 1982, Zeitschrift fur Operations Research, Serie A (Theorie), V26, P157, DOI 10.1007/BF01917108

[8]

Borgwardt K.-H., 1977, THESIS

[9]

Borgwardt K.-H., 12 S MATH PROGR CAMB

[10] SOME DISTRIBUTION-INDEPENDENT RESULTS ABOUT THE ASYMPTOTIC ORDER OF THE AVERAGE NUMBER OF PIVOT STEPS OF THE SIMPLEX-METHOD [J].

BORGWARDT, KH .

MATHEMATICS OF OPERATIONS RESEARCH, 1982, 7 (03) :441-462

← 1 2 3 4 →