Detecting community structure in complex networks using an interaction optimization process

被引:10
作者
Kim, Paul [1 ]
Kim, Sangwook [1 ]
机构
[1] Kyungpook Natl Univ, Sch Comp Sci & Engn, 401 IT-4,80 Daehakro, Daegu 702701, South Korea
基金
新加坡国家研究基金会;
关键词
Community detection; Interaction-based community; Interaction optimization process; Network structure analysis; Complex networks; ALGORITHM;
D O I
10.1016/j.physa.2016.08.012
中图分类号
O4 [物理学];
学科分类号
0702 ;
摘要
Most complex networks contain community structures. Detecting these community structures is important for understanding and controlling the networks. Most community detection methods use network topology and edge density to identify optimal communities; however, these methods have a high computational complexity and are sensitive to network forms and types. To address these problems, in this paper, we propose an algorithm that uses an interaction optimization process to detect community structures in complex networks. This algorithm efficiently searches the candidates of optimal communities by optimizing the interactions of the members within each community based on the concept of greedy optimization. During this process, each candidate is evaluated using an interaction based community model. This model quickly and accurately measures the difference between the quantity and quality of intra- and inter-community interactions. We test our algorithm on several benchmark networks with known community structures that include diverse communities detected by other methods. Additionally, after applying our algorithm to several real-world complex networks, we compare our algorithm with other methods. We find that the structure quality and coverage results achieved by our algorithm surpass those of the other methods. (C) 2016 Elsevier B.V. All rights reserved.
引用
收藏
页码:525 / 542
页数:18
相关论文
共 29 条
[1]   Link communities reveal multiscale complexity in networks [J].
Ahn, Yong-Yeol ;
Bagrow, James P. ;
Lehmann, Sune .
NATURE, 2010, 466 (7307) :761-U11
[2]  
[Anonymous], J STAT MECH
[3]   Fast unfolding of communities in large networks [J].
Blondel, Vincent D. ;
Guillaume, Jean-Loup ;
Lambiotte, Renaud ;
Lefebvre, Etienne .
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2008,
[4]   Models of social networks based on social distance attachment -: art. no. 056122 [J].
Boguñá, M ;
Pastor-Satorras, R ;
Díaz-Guilera, A ;
Arenas, A .
PHYSICAL REVIEW E, 2004, 70 (05) :8-1
[5]  
Clauset A, 2004, PHYS REV E, V70, DOI 10.1103/PhysRevE.70.066111
[6]   Reaction-diffusion processes and metapopulation models in heterogeneous networks [J].
Colizza, Vittoria ;
Pastor-Satorras, Romualdo ;
Vespignani, Alessandro .
NATURE PHYSICS, 2007, 3 (04) :276-282
[7]   Identifying Modular Flows on Multilayer Networks Reveals Highly Overlapping Organization in Interconnected Systems [J].
De Domenico, Manlio ;
Lancichinetti, Andrea ;
Arenas, Alex ;
Rosvall, Martin .
PHYSICAL REVIEW X, 2015, 5 (01)
[8]   Mixing local and global information for community detection in large networks [J].
De Meo, Pasquale ;
Ferrara, Emilio ;
Fiumara, Giacomo ;
Provetti, Alessandro .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2014, 80 (01) :72-87
[9]   Community detection in graphs [J].
Fortunato, Santo .
PHYSICS REPORTS-REVIEW SECTION OF PHYSICS LETTERS, 2010, 486 (3-5) :75-174
[10]  
Gregory S, 2008, LECT NOTES ARTIF INT, V5211, P408, DOI 10.1007/978-3-540-87479-9_45