A paradox in community detection
Center for Complex Networks and Systems Research, School of Informatics and Computing, Indiana University Bloomington, IN, USA
Received: 19 December 2013
Accepted: 11 April 2014
Recent research has shown that virtually all algorithms aimed at the identification of communities in networks are affected by the same main limitation: the impossibility to detect communities, even when these are well defined, if the average value of the difference between internal and external node degrees does not exceed a strictly positive value, in the literature known as detectability threshold. Here, we counterintuitively show that the value of this threshold is inversely proportional to the intrinsic quality of communities: the detection of well-defined modules is thus more difficult than the identification of ill-defined communities.
PACS: 89.75.Hc – Networks and genealogical trees / 02.70.Hm – Spectral methods / 64.60.aq – Networks
© EPLA, 2014