Geodesic
Combined neighborhood tabu search for community detection in complex networks
Gach, Olivier1  ; Hao, Jin-Kao1, 2 
1 LERIA, University of Angers, 2 Bd Lavoisier, 49045 Angers cedex 01, France.
2 Institut Universitaire de France, Paris, France.
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

Voir la notice de l'article provenant de la source Numdam

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2015046
Classification : 90-08, 90C27
Keywords: Community detection, heuristics, tabu search, graph partitioning, clustering, combinatorial optimization

Gach, Olivier 1 ; Hao, Jin-Kao 1, 2

1 LERIA, University of Angers, 2 Bd Lavoisier, 49045 Angers cedex 01, France.
2 Institut Universitaire de France, Paris, France. 
@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},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {2},
     year = {2016},
     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 :