Combined neighborhood tabu search for community detection in complex networks

Gach, Olivier; Hao, Jin-Kao

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.

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.

R. Albert and A.-L. Barabási, Statistical mechanics of complex networks. Rev. Mod. Phys. 74 (2002) 47. | DOI | MR | Zbl

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.

U. Benlic and J.K. Hao, A multilevel memetic approach for improving graph $k$-partitions. IEEE Trans. Evol. Comput. 15 (2011) 624-472. | DOI

V.D. Blondel, J.-L. Guillaume, R. Lambiotte and E. Lefebvre, Fast unfolding of communities in large networks. J. Stat. Mech. 10 (2008) 8.

S. Boccaletti, V. Latora, Y. Moreno, M. Chavez and D. Hwang, Complex networks: Structure and dynamics. Phys. Rep. 424 (2006) 175–308. | DOI | MR | Zbl

M. Boguñá, R. Pastor-Satorras, A. Díaz-Guilera and A. Arenas, Models of social networks based on social distance attachment. Phys. Rev. E 70 (2004) 056122. | DOI

U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski and D. Wagner, On modularity clustering, Knowl. Data Eng. 20 (2008) 172–188. | DOI

D. Bu, Y. Zhao, L. Cai, H. Xue, X. Zhu, H. Lu, J. Zhang, S. Sun, L. Ling and N. Zhang, 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.

A. Clauset, M.E.J. Newman and C. Moore, Finding community structure in very large networks. Phys. Rev. E 70 (2004) 066111. | DOI

L. Danon, A. Díaz-Guilera and A. Arenas, The effect of size heterogeneity on community identification in complex networks. J. Stat. Mech. 2006 (2006) P11010. | DOI

J. Duch and A. Arenas. Community detection in complex networks using extremal optimization. Phys. Rev. E 72 (2005) 027104. | DOI

S. Fortunato, Community detection in graphs. Phys. Rep. 486 (2010) 75–174. | DOI | MR

S. Fortunato and M. Barthélemy, 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.

M. Girvan and M.E.J. Newman, Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA 99 (2002) 7821–7826. | DOI | MR | Zbl

P. Gleiser and L. Danon, 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).

R. Guimerà, L. Danon, A. Díaz-Guilera, F. Giralt and A. Arenas, 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.

G. Karypis and V. Kumar, A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20 (1998) 359–392. | DOI | MR | Zbl

KDD. Cornell kdd cup. Available at http://www.cs.cornell.edu/projects/kddcup/ (2003).

B.W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs. Bell Syst. Technical J. 49 (1970) 291–307. | DOI | Zbl

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).

J. Leskovec, J. Kleinberg and C. Faloutsos, Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1 (2006) 2. | DOI

J. Leskovec, K.J. Lang, A. Dasgupta and M. Mahoney, 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).

Z. Lü and W. Huang, Iterated tabu search for identifying community structure in complex networks. Phys. Rev. E 80 (2009) 026130. | DOI

Z. Lü, J.K. Hao and F. Glover, Neighborhood analysis: a case study on curriculum-based course timetabling. J. Heuristics 17 (2011) 97118.

D. Lusseau, K. Schneider, O.J. Boisseau, P. Haase, E. Slooten and S.M. Dawson, The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations. Behav. Ecol. Sociobiol. 54 (2003) 396–405. | DOI

A.D. Medus and C.O. Dorso, Alternative approach to community detection in networks. Phys. Rev. E 79 (2009) 066111. | DOI

M.E.J. Newman, The structure of scientific collaboration networks. Proc. of Natl. Acad. Sci. USA 98 (2001) 404–409. | DOI | MR | Zbl

M.E.J. Newman, 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

M.E.J. Newman and M. Girvan, 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).

J. Reichardt and S. Bornholdt, Statistical mechanics of community detection. Phys. Rev. E 74 (2006) 1–14. | DOI | MR

R. Rotta, Email network. http://studiy.tu-cottbus.de/˜rrotta/

P. Schuetz and A. Caflisch, 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.

S.H. Strogatz, Exploring complex networks. Nature 410 (2001) 268–276. | DOI | Zbl

D.J. Watts and S.H. Strogatz, Collective dynamics of small-world networks. Nature 393 (1998) 440–2. | DOI

W.W. Zachary, An information flow model for conflict and fission in small groups. J. Anthropological Res. 33 (1977) 452–473. | DOI