Un)detectable Cluster Structure in Sparse Networks

Can a cluster structure in a sparse relational data set, i.e., a network, be detected at all by unsupervised clustering techniques? We answer this question by means of statistical mechanics making our analysis independent of any particular algorithm used for clustering. We find a sharp transition from a phase in which the cluster structure is not detectable at all to a phase in which it can be detected with high accuracy. We calculate the transition point and the shape of the transition, i.e., the theoretically achievable accuracy, analytically. This illuminates theoretical limitations of data mining in networks and allows for an understanding and evaluation of the performance of a variety of algorithms.