Volume 106, Number 3, May 2014
|Number of page(s)||5|
|Section||Interdisciplinary Physics and Related Areas of Science and Technology|
|Published online||07 May 2014|
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.