(Un)detectable cluster structure in sparse networks

Details (Un)detectable cluster structure in sparse networks (Un)detectable cluster structure in sparse networks

2007-11-09

arxiv.org/abs/0711.1452v1

Phys. Rev. Lett. 101, 078701 (2008)

Physics

Condensed Matter

Disordered Systems and Neural Networks

4 Pages, 2 Figures

Scientific paper

10.1103/PhysRevLett.101.078701

We study the problem of recovering a known cluster structure in a sparse network, also known as the planted partitioning problem, by means of statistical mechanics. We find a sharp transition from un-recoverable to recoverable structure as a function of the separation of the clusters. For multivariate data, such transitions have been observed frequently, but always as a function of the number of data points provided, i.e. given a large enough data set, two point clouds can always be recognized as different clusters, as long as their separation is non-zero. In contrast, for the sparse networks studied here, a cluster structure remains undetectable even in an infinitely large network if a critical separation is not exceeded. We give analytic formulas for this critical separation as a function of the degree distribution of the network and calculate the shape of the recoverability-transition. Our findings have implications for unsupervised learning and data-mining in relational data bases and provide bounds on the achievable performance of graph clustering algorithms.

Affiliated with

Also associated with

No associations

Rating

(Un)detectable cluster structure in sparse networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with (Un)detectable cluster structure in sparse networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and (Un)detectable cluster structure in sparse networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-702354