- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Multiscale ensemble clustering for finding modules in complex networks

Eun-Youn Kim, Dong-Uk Hwang, and Tae-Wook Ko*

  • Computational Neuroscience Team, National Institute for Mathematical Sciences, Daejeon 305-811, Republic of Korea

  • *Corresponding author: twko@nims.re.kr
PDF

Phys. Rev. E 85, 026119 – Published 27 February, 2012

DOI: https://doi.org/10.1103/PhysRevE.85.026119

Abstract

The identification of modules in complex networks is important for the understanding of systems. Here, we propose an ensemble clustering method incorporating node groupings in various sizes and the sequential removal of weak ties between nodes which are rarely grouped together. This method successfully detects modules in various networks, such as hierarchical random networks and the American college football network, with known modular structures. Some of the results are compared with those obtained by modularity optimization and K-means clustering.

View figure in article

Article Text

References (41)

  1. S. Fortunato, Phys. Rep. 486, 75 (2010).
  2. E. Bullmore and O. Sporns, Nat. Rev. Neurosci. 10, 186 (2009); O. Sporns, Networks of the Brain (MIT Press, Cambridge, MA, 2010).
  3. G. Zamora-López, C. Zhou, and J. Kurths, Front. Neuroinform. 4, 1 (2010); D. Meunier, R. Lambiotte, and E. Bullmore, Front. Neurosci. 4, 200 (2010).
  4. O. Sporns, G. Tononi, and R. Kötter, PLoS Comput. Biol. 1, e42 (2005).
  5. R. Guimerà and L. A. N. Amaral, Nature (London) 433, 895 (2005).
  6. A. Arenas, A. Díaz-Guilerac, J. Kurthsd, Y. Morenob, and C. Zhou, Phys. Rep. 469, 93 (2008).
  7. L. Huang, K. Park, and Y.-C. Lai, Phys. Rev. E 73, 035103(R) (2006).
  8. M. Kaiser and C. C. Hilgetag, Front. Neuroinform. 4, 8 (2010).
  9. R. Albert and A.-L. Barabasi, Rev. Mod. Phys. 74, 47 (2002); M. E. J. Newman, SIAM Rev. 45, 167 (2003); S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang, Phys. Rep. 424, 175 (2006).
  10. L. Danon, A. Díaz-Guilera1, J. Duch, and A. Arenas, J. Stat. Mech.: Theory Exp. (2005) P09008.
  11. A. Lancichinetti and S. Fortunato, Phys. Rev. E 80, 056117 (2009).
  12. H. Zhou, Phys. Rev. E 67, 061901 (2003).
  13. M. Girvan and M. E. J. Newman, Proc. Natl. Acad. Sci. USA 99, 7821 (2002).
  14. M. E. J. Newman and M. Girvan, Phys. Rev. E 69, 026113 (2004).
  15. A. Clauset, M. E. J. Newman, and C. Moore, Phys. Rev. E 70, 066111 (2004).
  16. G. Palla, I. Derényi, I. Farkas, and T. Vicsek, Nature (London) 435, 814 (2005).
  17. S. Boccaletti, M. Ivanchenko, V. Latora, A. Pluchino, and A. Rapisarda, Phys. Rev. E 75, 045102(R) (2007).
  18. M. Rosvall and C. T. Bergstrom, Proc. Natl. Acad. Sci. USA 104, 7327 (2007); 105, 1118 (2008).
  19. V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, J. Stat. Mech.: Theory Exp. (2008) P10008.
  20. A. Arenas, A. Fernández, and S. Gómez, New J. Phys. 10, 053039 (2008).
  21. P.-N. Tan, M. Steinbach, and V. Kumar, Introduction to Data Mining (Addison-Wesley, Boston, MA, 2005).
  22. M. Gustafsson, M. Hörnquist, and A. Lombardi, Physica A 367, 559 (2006).
  23. J. Liu and T. Liu, Physica A 389, 2300 (2010).
  24. M. Chavez, M. Valencia, V. Navarro, V. Latora, and J. Martinerie, Phys. Rev. Lett. 104, 118701 (2010).
  25. A. Strehl and J. Ghosh, J. Mach. Learn. Res. 3, 583 (2002), http://jmlr.csail.mit.edu/papers/v3/strehl02a.html.
  26. A. Fred and A. K. Jain, in Proceedings of the 16th International Conference on Pattern Recognition, Quebec, 2002, edited by R. Kasturi, D. Laurendeau, and C. Suen (IEEE Computer Society, Los Alamitos, CA, 2002), Vol. 4, p. 276; in Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Wisconsin, 2003 (IEEE Computer Society, Los Alamitos, CA, 2003), Vol. 2, p. 128.
  27. S. Monti, P. Tamayo, J. Mesirov, and T. Golub, Mach. Learn. 52, 91 (2003).
  28. D. Ashlock, E.-Y. Kim, and L. Guo, in Proceedings of the Artificial Neural Networks in Engineering Conference, St. Louis, USA, 2005, edited by C. H. Dagli, A. L. Buczak, M. J. Embrechts, and O. Ersoy (ASME, New York, 2005), Vol. 15, p. 453.
  29. E.-Y. Kim, S. –Y Kim, D. Ashlock, and D. Nam, BMC Bioinf. 10, 260 (2009).
  30. S. Fortunato and M. Barthélemy, Proc. Natl. Acad. Sci. USA 104, 36 (2007).
  31. M. Sales-Pardo, R. Guimerà, A. A. Moreira, and L. A. N. Amaral, Proc. Natl. Acad. Sci. USA 104, 15224 (2007).
  32. H. Kwak, Y. Choi, Y.-H. Eom, H. Jeong, and S. B. Moon, in Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement 2009, edited by A. Feldmann and L. Mathy (ACM, New York, 2009), p. 301; S. Moon, J. You, H. Kwak, D. Kim, and H. Jeong, in Proceedings of the 2nd International Conference on Communication Systems and Networks (IEEE, Piscataway, NJ, 2010), p. 317.
  33. E. Horowitz, S. Sahni, and S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed. (Silicon Press, Summit, NJ, 2007).
  34. M. E. J. Newman, Phys. Rev. E 70, 056131 (2004).
  35. C. Lee and D. Ashlock, in Proceedings of the IEEE Canadian Conference on Electrical and Computer Engineering, Niagara Falls, Canada, 2008 (IEEE, Piscataway, NJ, 2008), p. 847.
  36. R. Guimerà, L. Danon, A. Diaz-Guilera, F. Giralt, and A. Arenas, Phys. Rev. E 68, 065103(R) (2003).
  37. A. Lancichinetti, S. Fortunato, and F. Radicchi, Phys. Rev. E 78, 046110 (2008).
  38. http://sites.google.com/site/santofortunato/inthepress2.
  39. http://mlb.com.
  40. T. S. Evans, J. Stat. Mech.: Theory Exp. (2010) P12037.
  41. The corrected version [40] of the original college football network data [13] for the 2000 NCAA Division I-A football season can be downloaded from http://theory.ic.ac.uk/~time/networks/resources.html.

Outline

Information

Phys. Rev. E 85, 026119– Published 27 February, 2012
  • Received 21 October 2011

©2012 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation