Community is one prominent feature of complex networks. Community detection is one important research topic in the area of complex networks analysis. In this paper, we introduce a new heuristic algorithm for community detection using the popular modularity measure. The proposed algorithm, called CNTS for combined neighborhood tabu search (CNTS), relies on a joint use of vertex move and merge operators to improve the quality of visited solutions. A dedicated tabu mechanism provides the algorithm with additional capacities to effectively explore the search space. Experiments using a collection of 21 well-known benchmark instances show that the proposed algorithm competes favorably with state-of-the-art algorithms.
Accepté le :
DOI : 10.1051/ro/2015046
Keywords: Community detection, heuristics, tabu search, graph partitioning, clustering, combinatorial optimization
Gach, Olivier 1 ; Hao, Jin-Kao 1 , 2
@article{RO_2016__50_2_269_0,
author = {Gach, Olivier and Hao, Jin-Kao},
title = {Combined neighborhood tabu search for community detection in complex networks},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {269--283},
year = {2016},
publisher = {EDP-Sciences},
volume = {50},
number = {2},
doi = {10.1051/ro/2015046},
mrnumber = {3479868},
zbl = {1342.90228},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2015046/}
}
TY - JOUR AU - Gach, Olivier AU - Hao, Jin-Kao TI - Combined neighborhood tabu search for community detection in complex networks JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2016 SP - 269 EP - 283 VL - 50 IS - 2 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro/2015046/ DO - 10.1051/ro/2015046 LA - en ID - RO_2016__50_2_269_0 ER -
%0 Journal Article %A Gach, Olivier %A Hao, Jin-Kao %T Combined neighborhood tabu search for community detection in complex networks %J RAIRO - Operations Research - Recherche Opérationnelle %D 2016 %P 269-283 %V 50 %N 2 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro/2015046/ %R 10.1051/ro/2015046 %G en %F RO_2016__50_2_269_0
Gach, Olivier; Hao, Jin-Kao. Combined neighborhood tabu search for community detection in complex networks. RAIRO - Operations Research - Recherche Opérationnelle, Special issue: Research on Optimization and Graph Theory dedicated to COSI 2013 / Special issue: Recent Advances in Operations Research in Computational Biology, Bioinformatics and Medicine, Tome 50 (2016) no. 2, pp. 269-283. doi: 10.1051/ro/2015046
Cité par Sources :