- Access by Xinjiang University
Closed benchmarks for network community structure characterization
Phys. Rev. E 85, 026109 – Published 15 February, 2012
DOI: https://doi.org/10.1103/PhysRevE.85.026109
Abstract
Characterizing the community structure of complex networks is a key challenge in many scientific fields. Very diverse algorithms and methods have been proposed to this end, many working reasonably well in specific situations. However, no consensus has emerged on which of these methods is the best to use in practice. In part, this is due to the fact that testing their performance requires the generation of a comprehensive, standard set of synthetic benchmarks, a goal not yet fully achieved. Here, we present a type of benchmark that we call “closed,” in which an initial network of known community structure is progressively converted into a second network whose communities are also known. This approach differs from all previously published ones, in which networks evolve toward randomness. The use of this type of benchmark allows us to monitor the transformation of the community structure of a network. Moreover, we can predict the optimal behavior of the variation of information, a measure of the quality of the partitions obtained, at any moment of the process. This enables us in many cases to determine the best partition among those suggested by different algorithms. Also, since any network can be used as a starting point, extensive studies and comparisons can be performed using a heterogeneous set of structures, including random ones. These properties make our benchmarks a general standard for comparing community detection algorithms.
Article Text
References (26)
- S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications (Cambridge University Press, Cambridge, UK, 1994).
- S. H. Strogatz, Nature (London) 410, 6825 (2001).
- A.-L. Barabási and Z. N. Oltvai, Nat. Rev. Genet. 5, 101 (2004).
- M. E. J. Newman, Networks: An Introduction (Oxford University Press, New York, 2010).
- S. Fortunato, Phys. Rep. 486, 75 (2010).
- M. E. J. Newman and M. Girvan, Phys. Rev. E 69, 026113 (2004).
- R. Aldecoa and I. Marín, PloS ONE 6, e24195 (2011).
- M. Rosvall and C. T. Bergstrom, Proc. Natl. Acad. Sci. (USA) 105, 1118 (2008).
- P. Ronhovde and Z. Nussinov, Phys. Rev. E 80, 016109 (2009).
- M. E. J. Newman and E. A. Leicht, Proc. Natl. Acad. Sci. (USA) 104, 9564 (2007).
- A. Lancichinetti and S. Fortunato, Phys. Rev. E 80, 056117 (2009).
- A. Condon and R. M. Karp, Random Struct. Algorithms 18, 116 (2001).
- M. Girvan and M. E. J. Newman, Proc. Natl. Acad. Sci. (USA) 99, 7821 (2002).
- D. J. Watts, in Small Worlds. The Dynamics of Networks Between Order and Randomness (Princeton University Press, Princeton, NJ, 1999).
- R. Aldecoa and I. Marín, PLoS ONE 5, e11585 (2010).
- P. Erdos and A. Renyi, Publ. Math. 6, 290 (1959).
- A.-L. Barabási and R. Albert, Science 286, 509 (1999).
- S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D. U. Hwang, Phys. Rep. 424, 175 (2006).
- A. Lancichinetti, S. Fortunato, and F. Radicchi, Phys. Rev. E 78, 046110 (2008).
- N. X. Vinh, J. Epps, and J. Bailey, J. Mach. Learn. Res. 11, 2837 (2010).
- M. Meila, J. Multivariate Anal. 98, 873 (2007).
- S. Fortunato and M. Barthélemy, Proc. Natl. Acad. Sci. (USA) 104, 36 (2007).
- E. C. Pielou, J. Theor. Biol. 13, 131 (1966).
- V. Arnau, S. Mars, and I. Marín, Bioinformatics 21, 3 (2005).
- B. Karrer, E. Levina, and M. E. J. Newman, Phys. Rev. E 77, 046119 (2008).
- A. Lancichinetti, F. Radicchi, J. Ramasco, and S. Fortunato, PLoS ONE 6, e18961 (2011).