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.
Accepted:
DOI: 10.1051/ro/2015046
Keywords: Community detection, heuristics, tabu search, graph partitioning, clustering, combinatorial optimization
@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://archive.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 - http://archive.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 http://archive.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, Volume 50 (2016) no. 2, pp. 269-283. doi : 10.1051/ro/2015046. http://archive.numdam.org/articles/10.1051/ro/2015046/
Statistical mechanics of complex networks. Rev. Mod. Phys. 74 (2002) 47. | DOI | MR | Zbl
and ,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.
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. | DOI | MR | Zbl
, , , 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
, , , , , , , , and ,E. Cho, Seth A. Myers and J. Leskovec, Friendship and Mobility. ACM Press (2011) 1082.
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
and .Community detection in graphs. Phys. Rep. 486 (2010) 75–174. | DOI | MR
,Resolution limit in community detection. Proc. Natl. Acad. Sci. 104 (2007) 36–41. | DOI
and ,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.
Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99 (2002) 7821–7826. | DOI | MR | Zbl
and ,Community structure in social and biological networks. Adv. Complex Syst. 6 (2003) 565–573.
and ,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).
Self-similar community structure in a network of human interactions. Phys. Rev. E 68 (2003) 065103. | DOI
, , , and ,J. Heymann and S. Palmier, Source code structure of a java program. Available at http://wiki.gephi.org/index.php/Datasets.
A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20 (1998) 359–392. | DOI | MR | Zbl
and ,KDD. Cornell kdd cup. Available at http://www.cs.cornell.edu/projects/kddcup/ (2003).
An efficient heuristic procedure for partitioning graphs. Bell Syst. Technical J. 49 (1970) 291–307. | DOI | Zbl
and ,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).
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
, , and ,X. Liu and T. Murata, Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Physica A (2009).
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
and ,The structure of scientific collaboration networks. Proc. of Natl. Acad. Sci. USA 98 (2001) 404–409. | DOI | MR | Zbl
,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
Finding and evaluating community structure in networks. Phys. Rev. E 69 (2004) 026113. | DOI
and ,A. Noack and R. Rotta, Multi-level algorithms for modularity clustering. Preprint arXiv: 0812.4073 (2008).
Statistical mechanics of community detection. Phys. Rev. E 74 (2006) 1–14. | DOI | MR
and ,R. Rotta, Email network. http://studiy.tu-cottbus.de/˜rrotta/
Efficient modularity optimization by multistep greedy algorithm and vertex mover refinement. Phys. Rev. E 77 (2008) 046112. | DOI
and ,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. | DOI | Zbl
,Collective dynamics of small-world networks. Nature 393 (1998) 440–2. | DOI
and ,An information flow model for conflict and fission in small groups. J. Anthropological Res. 33 (1977) 452–473. | DOI
,Cited by Sources: