Physics – Data Analysis – Statistics and Probability
Scientific paper
2011-01-21
J. Stat. Mech. (2011) P08009
Physics
Data Analysis, Statistics and Probability
8 pages, 4 figures
Scientific paper
10.1088/1742-5468/2011/08/P08009
We theoretically study semi-supervised clustering in sparse graphs in the presence of pairwise constraints on the cluster assignments of nodes. We focus on bi-cluster graphs, and study the impact of semi-supervision for varying constraint density and overlap between the clusters. Recent results for unsupervised clustering in sparse graphs indicate that there is a critical ratio of within-cluster and between-cluster connectivities below which clusters cannot be recovered with better than random accuracy. The goal of this paper is to examine the impact of pairwise constraints on the clustering accuracy. Our results suggests that the addition of constraints does not provide automatic improvement over the unsupervised case. When the density of the constraints is sufficiently small, their only impact is to shift the detection threshold while preserving the criticality. Conversely, if the density of (hard) constraints is above the percolation threshold, the criticality is suppressed and the detection threshold disappears.
Allahverdyan Armen E.
Galstyan Aram
Steeg Greg Ver
No associations
LandOfFree
Statistical Mechanics of Semi-Supervised Clustering in Sparse Graphs 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 Statistical Mechanics of Semi-Supervised Clustering in Sparse Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Statistical Mechanics of Semi-Supervised Clustering in Sparse Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-642257