Abstract
In order to further improve the performance of current genetic algorithms aiming at discovering communities, a local search based genetic algorithm (GALS) is here proposed. The core of GALS is a local search based mutation technique. In order to overcome the drawbacks of traditional mutation methods, the paper develops the concept of marginal gene and then the local monotonicity of modularity function Q is deduced from each node’s local view. Based on these two elements, a new mutation method combined with a local search strategy is presented. GALS has been evaluated on both synthetic benchmarks and several real networks, and compared with some presently competing algorithms. Experimental results show that GALS is highly effective and efficient for discovering community structure.
Article PDF
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
D. J. Watts, and S. H. Strogatz, “Collective dynamics of small-world networks,” Nature, vol. 393, pp. 440–442, Jun. 1998.
A. L. Barabási, R. Albert, H. Jeong, and G. Bianconi, “Power-law distribution of the world wide web,” Science, vol. 287, pp. 2115a, Mar. 2000.
M. Girvan, and M. E. J. Newman. “Community structure in social and biological networks,” Proc. Natl. Acad. Sci. , vol. 99, pp. 7821–7826, Jun. 2002.
L. Danon, J. Duch, A. Diaz-Guilera, and A. Arenas, “Comparing community structure identification,” J. Stat. Mech. , vol. 2005, pp. P09008, Sep. 2005.
M. E. J. Newman, and M. Girvan, “Finding and evaluating community structure in networks,” Phys. Rev. E, vol. 69, pp. 026113, Feb. 2004.
S. Fortunato, “Community detection in graphs,” Phys. Rep. , vol. 486, pp. 75–174, Jun. 2010.
S. Fortunato, and M. Barthélemy, “Resolution limit in community detection,” Proc. Natl. Acad. Sci. , vol. 104, pp. 36–41, Jan. 2007.
B. H. Good, Y. -A. de Montjoye, and A. Clauset, “The performance of modularity maximization in practical contexts,” Phys. Rev. E, vol. 81, pp. 046106, Apr. 2010.
R. Guimera, M. Sales-Pardo, and L. A. N. Amaral, “Modularity from fluctuations in random graphs and complex networks,” Phys. Rev. E, vol. 70, pp. 025101, Aug. 2004.
U. Brandes, D. Delling, M. Gaertler, R. Goerke, M. Hoefer, Z. Nikoloski, and D. Wagner, “Maximizing modularity is hard,” arXiv:physics/0608255, 2006.
Y. J. Park, and M. S. Song, “A genetic algorithm for clustering problems,” in Proc. 3rd Annual Conference on Genetic Programming (GP’98), Madison, USA, 1998, pp. 568–575.
E. M. Montes, and C. A. C. Coello, “A simple multi-membered evolution strategy to solve constrained optimization problems,” IEEE Trans. Evolutionary Computation, vol. 9, pp. 1–17, Feb. 2005.
G. Syswerda, “Uniform crossover in genetic algorithms,” in Proc. 3rd International Conference on Genetic Algorithms (ICGA’89), Fairfax, Virginia, USA, 1989, pp. 2–9.
M. E. J. Newman, “Fast algorithm for detecting community structure in networks,” Phys. Rev. E, vol. 69, pp. 066133, Jun. 2004.
R. Guimera, and L. A. N. Amaral, “Functional cartography of complex metabolic networks,” Nature, vol. 433, pp. 895–900, Feb. 2005.
V. D. Blondel, J. L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks,” J. Stat. Mech. , vol. 2008, pp. P10008, Oct. 2008.
U. N. Raghavan, R. Albert, and S. Kumara, “Near linear-time algorithm to detect community structures in large-scale networks,” Phys. Rev. E, vol. 76, pp. 036106, Sep. 2007.
L. D. F. Costa, “Hub-based community finding,” arXiv:cond-mat/0405022v1, 2004.
J. P. Bagrow, and E. M. Bollt, “Local method for detecting communities,” Phys. Rev. E. , vol. 72, pp. 046108, Oct. 2005.
B. Yang, W. K. Cheung, and J. Liu, “Community mining from signed social networks,” IEEE Trans. Knowl. Data Eng. , vol. 19, pp. 1333–1348, Sep. 2007.
M. Rosvall, and C. T. Bergstrom, “Maps of random walks on complex networks reveal community structure,” Proc. Natl. Acad. Sci. , vol. 105, pp. 1118–1123, Jan. 2008.
P. Ronhovde, and Z. Nussinov, “Multiresolution community detection for megascale networks by information-based replica correlations,” Phys. Rev. E, vol. 80, pp. 016109, Jul. 2009.
M. Tasgin, A. Herdagdelen, and H. Bingol, “Community detection in complex networks using genetic algorithms,” arXiv:0711.0491, 2007.
D. He, Z. Wang, B. Yang, and C. Zhou, “Genetic algorithm with ensemble learning for detecting community structure in complex networks,” in Proc. IEEE Int. Conference on Computer Sciences and Convergence Information Technology (ICCIT’09), Seoul, Korea, 2009, pp. 702–707.
S. Li, Y. Chen, H. Du, and M. W. Feldman,”A genetic algorithm with local search strategy for improved detection of community structure,” Complexity, vol. 15, pp. 53–60, Mar. 2010.
C. Pizzuti, “Community detection in social networks with genetic algorithms,” in Proc. Genetic and Evolutionary Computation Conference (GECCO’08), Atlanta, Georgia, USA, 2008, pp. 1137–1138.
C. Pizzuti, “A multi-objective genetic algorithm for community detection in networks,” in Proc. IEEE Int. Conference on Tools with Artificial Intelligence (ICTAI’09), Washington, DC, USA, 2009, pp. 379-386.
C. Shi, Z. Yan, Y. Wang, Y. Cai, and B. Wu, “A genetic algorithm for detecting communities in large-scale complex networks,” Adv. Complex Systems, vol. 13, pp. 3–17, Jan. 2010.
G. Palla, I. Derenyi, I. Farkas, and T. Vicsek, “Uncovering the overlapping community structures of complex networks in nature and society,” Nature, vol. 435, pp. 814–818, Jun. 2005.
J. Handle and J. Knowles, “An evolutionary approach to multiobjective clustering,” IEEE Trans. Evolutionary Computation, vol. 11, pp. 56–76, Feb. 2007.
N. Makate, M. Miki, T. Hiroyasu, and T. Senda, “Multiobjective clustering with automatic k-determination for large-scale data,” in Proc. Genetic and Evolutionary Computation Conference (GECCO’07), London, England, 2007, pp. 861–868.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. Cambridge, MA: MIT Press, 2001.
P. Pons, and M. Latapy, “Computing communities in large networks using random walks,” Journal of Graph Algorithms and Applications, vol. 10, pp. 191–218, Jan. 2006.
A. Lancichinetti, S. Fortunato, and F. Radicchi, “Benchmark graphs for testing community detection algorithms,” Phys. Rev. E, vol. 78, pp. 046110, Oct. 2008.
J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney, “Statistical properties of community structure in large social and information networks,” in Proc. 17th International World Wide Web Conference (WWW’08), Beijing, China, 2008, pp. 695–704.
W. W. Zachary, “An information flow model for conflict and fission in small groups,” J. Anthropological Research, vol. 33, pp. 452–473, 1977.
D. Lusseau, “The emergent properties of a dolphin social network,” Proc Biol Sci, vol. 270, pp. S186–8, Jul. 2003.
M. E. J. Newman, “Modularity and community structure in networks,” Proc. Natl. Acad. Sci. , vol. 103, pp. 8577–8582, Jun. 2006.
P. M. Gleiser, and L. Danon, “Community structure in jazz,” Adv. Complex Systems, vol. 6, pp. 565–573, Jul. 2003.
R. Guimerà, L. Danon, A. Diaz-Guilera, F. Giralt, and A. Arenas, “Self-similar community structure in a network of human interactions,” Phys. Rev. E, vol. 68, pp. 065103, Dec. 2003.
Network data from Mark Newman’s home page, (2006). [Online]. Available: http://www-personal.umich.edu/~mejn/netdata/
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
About this article
Cite this article
Liu, D., Jin, D., Baquero, C. et al. Genetic Algorithm with a Local Search Strategy for Discovering Communities in Complex Networks. Int J Comput Intell Syst 6, 354–369 (2013). https://doi.org/10.1080/18756891.2013.773175
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1080/18756891.2013.773175