Evaluating community detection methods in a controlled experiment

摘要

Detecting communities in non-trivial networks is a hard task that has been attracting the attention of many researchers in the field of complex networks. When the network has identical and non-overlapping communities, however, one could expect this task to be easy. We show in this paper that, surprisingly, it is not the case. For this purpose, we carried out a controlled experiment in which 9 well-known community detection methods are applied to 8 different hierarchical ring networks of 60 nodes each. None of the tested methods correctly identified the communities for all networks. Moreover, the modularity score showed a weak response in the identification of rings as communities in hierarchical ring networks. These results point to the need of discussing what community detection algorithms are actually detecting, and how to evaluate their results, both when dealing with trivial or non-trivial networks.