Analysis of Communities Detection Algorithms in Complex Networks

Print
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2017
Authors:
Moises Bruno L. Bissoto, Ary Henrique M. Oliveira, Glenda M. Botelho
10.5120/ijca2017915356

Moises Bruno L Bissoto, Ary Henrique M Oliveira and Glenda M Botelho. Analysis of Communities Detection Algorithms in Complex Networks. International Journal of Computer Applications 173(7):1-7, September 2017. BibTeX

@article{10.5120/ijca2017915356,
	author = {Moises Bruno L. Bissoto and Ary Henrique M. Oliveira and Glenda M. Botelho},
	title = {Analysis of Communities Detection Algorithms in Complex Networks},
	journal = {International Journal of Computer Applications},
	issue_date = {September 2017},
	volume = {173},
	number = {7},
	month = {Sep},
	year = {2017},
	issn = {0975-8887},
	pages = {1-7},
	numpages = {7},
	url = {http://www.ijcaonline.org/archives/volume173/number7/28344-2017915356},
	doi = {10.5120/ijca2017915356},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

Abstract

Complex networks are an imminent multidisciplinary field defined by graphs that present a nontrivial topographic structure. An important information extracted from a complex network is its communities structure. In the literature, there are several communities detection algorithms, however, new research have emerged with the aim of detecting communities efficiently and with lower computational cost. Therefore, this work analyzes different algorithms for communities detection in complex networks with different characteristics, considering the Modularity measure, the execution time and the obtained communities number. The partitions obtained by the different algorithms presented high modularity values and it was observed that the influence of the number of vertices and edges in the execution time of some detection algorithms.

References

  1. Barabsi AL. Linked: How everything is connected to everything else and what it means for business, science, and everyday life. Basic Books, 2014.
  2. A. F. Angelis. Redes complexas (complex networks). Technical report, So Paulo University, 2005.
  3. James Bagrow and E.M. Bollt. A local method for detecting communities. 72:046108, 11 2005.
  4. A. Clauset, M. E. J. Newman, and C. Moore. Finding community structure in very large networks. Physical Review E, APS, 70(6):1–6, aug 2004.
  5. G. Csardi and T. Nepusz. The igraph software package for complex network research. Inter Journal, Complex Systems, 1695(5), 2006.
  6. J. Duch and A. Arenas. Community detection in complex networks using extremal optimization. Physical Review E, APS, 72(2):145–157, 2005.
  7. J. G. White et al. The structure of the nervous system of the nematode caenorhabditis elegans. In Philosophical Transactions of the Royal Society of London, volume 314, pages 1– 340. Biological Sciences, 1986.
  8. L. F. Costa et al. Characterization of complex networks: A survey of measurements. Advances in Physics, volume 56. Taylor & Franciss, 2014.
  9. M. Girvan and M. E. J. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, National Acad Sciences, 99(12):7821– 7826, 2002.
  10. A. K. Jain and R. C. Dubes. Algorithms for Clustering Data. Prentice Hall, 1988.
  11. C. P. Massen and J. P. K. Doye. Identifying communities within energy landscapes. Physical Review E, APS, 71(4):145–157, 2005.
  12. M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45(2):167–256, 2003.
  13. M. E. J. Newman. Fast algorithm for detecting community structure in networks. Physical Review E, APS, 69:1–5, 2006.
  14. M. E. J. Newman. Finding community structure in networks using the eigenvectors of matrices. Physics Review E, APS, 74(3):1–22, jan 2006.
  15. M. E. J. Newman. Modularity and community structure in networks. National Academy of Sciences of the USA, 103(23):85778582, 2006.
  16. M. E. J. Newman and M. Girvan. Finding and evaluating community structure in networks. Physical Review E, APS, 69(2):026113, 2004.
  17. P. Pons and M. Latapy. Computing communities in large networks using random walks. Journal of Graph Algorithms and Applications, 10(2):191–218, 2006.
  18. J. Reichadt and S. Bornholdt. Statistical mechanics of community detection. Physical Review E, 74:1–16, 2006.
  19. D. Stauffer, A. Aharony, L. da Fontoura Costa, and J. Adler. Effcient hopfeld pattern recognition on a scale-free neural network. The European Physical Journal B-Condensed Matter and Complex Systems, 32(3):395–399, 2003.
  20. W. W. Zachary. An information flow model for conflict and fission in small groups. Anthropological Research, 33:452473, 1977.

Keywords

Complex networks, Community detection algorithms, Modularity measure, Evaluation