Mixing Network Extremal Optimization for Community Structure Detection | SpringerLink
Skip to main content
Springer Nature Link
Log in

Mixing Network Extremal Optimization for Community Structure Detection

  • Conference paper
  • First Online:
Evolutionary Computation in Combinatorial Optimization (EvoCOP 2015)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 9026))

Abstract

Mixing Network Extremal Optimization is a new algorithm designed to identify the community structure in networks by using a game theoretic approach and a network mixing mechanism as a diversity preserving method. Numerical experiments performed on synthetic and real networks illustrate the potential of the approach.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5491
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 6864
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Generated with the code available at http://sites.google.com/site/andrealancichinetti/files, downloaded on March 2014.

  2. 2.

    For the algorithms we use the code and parameter setting available at https://sites.google.com/site/andrealancichinetti/software, downloaded on March 2014.

References

  1. Fortunato, S.: Community detection in graphs. Phys. Rep. 486, 75–174 (2010)

    Article  MathSciNet  Google Scholar 

  2. Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., Parisi, D.: Defining and identifying communities in networks. Proc. Natl. Acad. Sci. U.S.A 101(9), 2658–2663 (2004)

    Article  Google Scholar 

  3. Wasserman, S., Faust, K.: Social Network Analysis: Methods and Applications, vol. 8. Cambridge University Press, Cambridge (1994)

    Book  Google Scholar 

  4. Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. 99(12), 7821–7826 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  5. Nascimento, M.C., Pitsoulis, L.: Community detection by modularity maximization using GRASP with path relinking. Comput. Oper. Res. 40(12), 3121–3131 (2013)

    Article  MathSciNet  Google Scholar 

  6. Shang, R., Bai, J., Jiao, L., Jin, C.: Community detection based on modularity and an improved genetic algorithm. Phys. A: Stat. Mech. Appl. 392(5), 1215–1231 (2013)

    Article  Google Scholar 

  7. Honghao, C., Zuren, F., Zhigang, R.: Community detection using ant colony optimization. In: 2013 IEEE Congress on Evolutionary Computation (CEC), pp. 3072–3078 (2013)

    Google Scholar 

  8. Shi, C., Yan, Z., Cai, Y., Wu, B.: Multi-objective community detection in complex networks. Appl. Soft Comput. 12(2), 850–859 (2012)

    Article  Google Scholar 

  9. Li, Z., Zhang, S., Wang, R.S., Zhang, X.S., Chen, L.: Quantitative function for community detection. Phys. Rev. E 77, 036109 (2008)

    Article  Google Scholar 

  10. Gong, M., Fu, B., Jiao, L., Du, H.: Memetic algorithm for community detection in networks. Phys. Rev. E 84, 056101 (2011)

    Article  Google Scholar 

  11. Jiang, J.Q., McQuay, L.J.: Modularity functions maximization with nonnegative relaxation facilitates community detection in networks. Phys. A: Stat. Mech. Appl. 391(3), 854–865 (2012)

    Article  Google Scholar 

  12. Gong, M., Ma, L., Zhang, Q., Jiao, L.: Community detection in networks by using multiobjective evolutionary algorithm with decomposition. Phys. A: Stat. Mech. Appl. 391(15), 4050–4060 (2012)

    Article  Google Scholar 

  13. Gong, M., Cai, Q., Chen, X., Ma, L.: Complex network clustering by multiobjective discrete particle swarm optimization based on decomposition. IEEE Trans. Evol. Comput. 18(99), 82–97 (2013)

    Google Scholar 

  14. Angelini, L., Boccaletti, S., Marinazzo, D., Pellicoro, M., Stramaglia, S.: Identification of network modules by optimization of ratio association. Chaos: An Interdisc. J. Nonlinear Sci. 17(2), 023114 (2007)

    Article  Google Scholar 

  15. Pizzuti, C.: GA-Net: a genetic algorithm for community detection in social networks. In: Rudolph, G., Jansen, T., Lucas, S., Poloni, C., Beume, N. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 1081–1090. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  16. Lancichinetti, A., Fortunato, S., Kertész, J.: Detecting the overlapping and hierarchical community structure in complex networks. New J. Phys. 11(3), 033015 (2009)

    Article  Google Scholar 

  17. Amiri, B., Hossain, L., Crawford, J.W., Wigand, R.T.: Community detection in complex networks: multi-objective enhanced firefly algorithm. Knowl.-Based Syst. 46, 1–11 (2013)

    Article  Google Scholar 

  18. Pizzuti, C.: A multiobjective genetic algorithm to find communities in complex networks. IEEE Trans. Evol. Comput. 16(3), 418–430 (2012)

    Article  Google Scholar 

  19. Lancichinetti, A., Fortunato, S.: Limits of modularity maximization in community detection. Phys. Rev. E 84, 066122 (2011)

    Article  Google Scholar 

  20. Chira, C., Gog, A., Iclanzan, D.: Evolutionary detection of community structures in complex networks: A new fitness function. In: IEEE Congress on Evolutionary Computation (CEC), 2012, pp. 1–8. IEEE (2012)

    Google Scholar 

  21. Lung, R.I., Chira, C., Andreica, A.: Game theory and extremal optimization for community detection in complex dynamic networks. PLOS ONE 9(2), e86891 (2014)

    Article  Google Scholar 

  22. Lung, R.I., Dumitrescu, D.: Computing nash equilibria by means of evolutionary computation. Int. J. Comput. Commun. Control III(suppl.issue), 364–368 (2008)

    Google Scholar 

  23. Lung, R.I., Mihoc, T.D., Dumitrescu, D.: Nash equilibria detection for multi-player games. In: IEEE Congress on Evolutionary Computation, 1–5 (2010)

    Google Scholar 

  24. Lung, R.I., Mihoc, T.D., Dumitrescu, D.: Nash extremal optimization and large cournot games. In: Pelta, D.A., Krasnogor, N., Dumitrescu, D., Chira, C., Lung, R. (eds.) NICSO 2011. SCI, vol. 387, pp. 195–203. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  25. Boettcher, S., Percus, A.G.: Optimization with extremal dynamics. Phys. Rev. Lett. 86, 5211–5214 (2001)

    Article  Google Scholar 

  26. Maslov, S., Sneppen, K.: Specificity and stability in topology of protein networks. Sci. 296, 910–913 (2002)

    Article  Google Scholar 

  27. Lancichinetti, A., Fortunato, S.: Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys. Rev. E 80, 016118 (2009)

    Article  Google Scholar 

  28. Lancichinetti, A., Radicchi, F., Ramasco, J.J., Fortunato, S.: Finding statistically significant communities in networks. PloS one 6(4), e18961 (2011)

    Article  Google Scholar 

  29. Rosvall, M., Bergstrom, C.T.: Maps of random walks on complex networks reveal community structure. Proc. Natl. Acad. Sci. 105(4), 1118–1123 (2008)

    Article  Google Scholar 

  30. Sales-Pardo, M., Guimer, R., Moreira, A., Nunes Amaral, L.: Extracting the hierarchical organization of complex systems. Proc. Natl. Acad. Sci. U.S.A. 104(39), 15224–15229 (2007)

    Article  Google Scholar 

  31. Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech.: Theory Exp. 2008(10), P10008 (2008)

    Article  Google Scholar 

Download references

Acknowledgment

This work was supported by the project “OPEN-RES (PN-II-PC-CA-2011-3.1-0682 212/2.07.2012).”

Author information

Authors and Affiliations

  1. Department of Computer Science, Babeş-Bolyai University, Cluj Napoca, Romania

    Mihai Suciu & Noémi Gaskó

  2. Faculty of Economics and Business Administration, Babeş-Bolyai University, Cluj Napoca, Romania

    Rodica Ioana Lung

Authors
  1. Mihai Suciu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rodica Ioana Lung
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Noémi Gaskó
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mihai Suciu .

Editor information

Editors and Affiliations

  1. University of Stirling, Stirling, United Kingdom

    Gabriela Ochoa

  2. University of Málaga, Málaga, Spain

    Francisco Chicano

Rights and permissions

Reprints and permissions

Copyright information

© 2015 Springer International Publishing Switzerland

About this paper

Cite this paper

Suciu, M., Lung, R.I., Gaskó, N. (2015). Mixing Network Extremal Optimization for Community Structure Detection. In: Ochoa, G., Chicano, F. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2015. Lecture Notes in Computer Science(), vol 9026. Springer, Cham. https://doi.org/10.1007/978-3-319-16468-7_11

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-16468-7_11

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-16467-0

  • Online ISBN: 978-3-319-16468-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation