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 = {https://www.numdam.org/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 - https://www.numdam.org/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 https://www.numdam.org/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
and , Statistical mechanics of complex networks. Rev. Mod. Phys. 74 (2002) 47. | MR | Zbl | DOI
A. Barrat, M. Barthlemy and A. Vespignani, Dynamical Processes on Complex Networks. Cambridge University Press (2008). | MR | Zbl
V. Batagelj and A. Mrvar, Email network. http://vlado.fmf.uni-lj.si/pub/networks/data/default.htm.
and , A multilevel memetic approach for improving graph -partitions. IEEE Trans. Evol. Comput. 15 (2011) 624-472. | DOI
, , and , Fast unfolding of communities in large networks. J. Stat. Mech. 10 (2008) 8.
, , , and , Complex networks: Structure and dynamics. Phys. Rep. 424 (2006) 175–308. | MR | Zbl | DOI
, , and , Models of social networks based on social distance attachment. Phys. Rev. E 70 (2004) 056122. | DOI
, , , , , and , On modularity clustering, Knowl. Data Eng. 20 (2008) 172–188. | DOI
, , , , , , , , and , Topological structure analysis of the protein-protein interaction network in budding yeast. Nucleic Acids Research 31 (2003) 2443–2450. | DOI
E. Cho, Seth A. Myers and J. Leskovec, Friendship and Mobility. ACM Press (2011) 1082.
, and , Finding community structure in very large networks. Phys. Rev. E 70 (2004) 066111. | DOI
, and , The effect of size heterogeneity on community identification in complex networks. J. Stat. Mech. 2006 (2006) P11010. | DOI
and . Community detection in complex networks using extremal optimization. Phys. Rev. E 72 (2005) 027104. | DOI
, Community detection in graphs. Phys. Rep. 486 (2010) 75–174. | MR | DOI
and , Resolution limit in community detection. Proc. Natl. Acad. Sci. 104 (2007) 36–41. | DOI
O. Gach and J.K. Hao, A memetic algorithm for community detection in complex networks. In PPSN 2012. Edited by C. Coello et al. Vol. 7492 of Lect. Notes Comput. Sci. (2012) 327–336.
O. Gach and J.K. Hao, Improving the Louvain algorithm for community detection with modularity maximization. In Conf. of AE 2013. Edited by P. Legrand et al. In vol. 8752 of Lect. Notes Comput. Sci. (2014) 145–156.
and , Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99 (2002) 7821–7826. | MR | Zbl | DOI
and , Community structure in social and biological networks. Adv. Complex Syst. 6 (2003) 565–573.
F. Glover and M. Laguna, Tabu Search. In Modern Heuristic Techniques for Combinatorial Problems. Edited by C. Reeves. Blackwell Scientific Publishing, Oxford, England (1993). | MR
J. Grossman, The erdös number project. Available at http://www.oakland.edu/enp/ (2007).
, , , and , Self-similar community structure in a network of human interactions. Phys. Rev. E 68 (2003) 065103. | DOI
J. Heymann and S. Palmier, Source code structure of a java program. Available at http://wiki.gephi.org/index.php/Datasets.
and , A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20 (1998) 359–392. | MR | Zbl | DOI
KDD. Cornell kdd cup. Available at http://www.cs.cornell.edu/projects/kddcup/ (2003).
and , An efficient heuristic procedure for partitioning graphs. Bell Syst. Technical J. 49 (1970) 291–307. | Zbl | DOI
J. Kleinberg, A network of pages linking www.epa.gov in a search engine. Available at http://www.cs.cornell.edu/courses/cs685/2002fa/.
J. Kleinberg, A network of pages matching the query “california” in a search engine. Available at http://www.cs.cornell.edu/courses/cs685/2002fa/.
V. Krebs, A network of books about recent us politics sold by the online bookseller amazon.com. Available at http://www.orgnet.com (2008).
, and , Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1 (2006) 2. | DOI
, , and , Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Math. 6 (2008) 66. | MR | Zbl
X. Liu and T. Murata, Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Physica A (2009).
and , Iterated tabu search for identifying community structure in complex networks. Phys. Rev. E 80 (2009) 026130. | DOI
, and , Neighborhood analysis: a case study on curriculum-based course timetabling. J. Heuristics 17 (2011) 97118.
, , , , and , The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. Behav. Ecol. Sociobiol. 54 (2003) 396–405. | DOI
and , Alternative approach to community detection in networks. Phys. Rev. E 79 (2009) 066111. | DOI
, The structure of scientific collaboration networks. Proc. of Natl. Acad. Sci. USA 98 (2001) 404–409. | MR | Zbl | DOI
, Fast algorithm for detecting community structure in networks. Phys. Rev. E 69 (2004) 066133. | DOI
M.E.J. Newman, Networks: An Introduction. Oxford University Press (2010). | MR | Zbl
and , Finding and evaluating community structure in networks. Phys. Rev. E 69 (2004) 026113. | DOI
A. Noack and R. Rotta, Multi-level algorithms for modularity clustering. Preprint arXiv: 0812.4073 (2008).
and , Statistical mechanics of community detection. Phys. Rev. E 74 (2006) 1–14. | MR | DOI
R. Rotta, Email network. http://studiy.tu-cottbus.de/˜rrotta/
and , Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement. Phys. Rev. E 77 (2008) 046112. | DOI
P. Schuetz and A. Caflisch, Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement 77 (2008) 046112.
, Exploring complex networks. Nature 410 (2001) 268–276. | Zbl | DOI
and , Collective dynamics of small-world networks. Nature 393 (1998) 440–2. | DOI
, An information flow model for conflict and fission in small groups. J. Anthropological Res. 33 (1977) 452–473. | DOI
Cité par Sources :
