  We present a detailed theoretical and computational analysis of the Watset
meta-algorithm for fuzzy graph clustering, which has been found to be widely
applicable in a variety of domains. This algorithm creates an intermediate
representation of the input graph that reflects the "ambiguity" of its nodes.
Then, it uses hard clustering to discover clusters in this "disambiguated"
intermediate graph. After outlining the approach and analyzing its
computational complexity, we demonstrate that Watset shows competitive results
in three applications: unsupervised synset induction from a synonymy graph,
unsupervised semantic frame induction from dependency triples, and unsupervised
semantic class induction from a distributional thesaurus. Our algorithm is
generic and can be also applied to other networks of linguistic data.
