search

benedekrozemberczki / awesome-community-detection

A curated list of community detection research papers with implementations.
Creative Commons Zero v1.0 Universal
2.33k stars 361 forks source link

Add Watset overlapping community detection algorithm #2

Closed dustalov closed 5 years ago

dustalov commented 5 years ago

This pull request adds one more overlapping community detection algorithm, Watset, to the “Other” category.

benedekrozemberczki commented 5 years ago

This does not seem to be an overlapping community detection procedure.

dustalov commented 5 years ago

Only at a first glance. Watset was originally designed for the synset induction problem, which implies clustering of a synonymy graph. Each resulting cluster, called a synset, contains words with the same meaning. Of course, these clusters overlap in case of polysemous words.

Look at Figure 2 in the original Watset paper. The algorithm transforms the input graph into a sense-aware representation and then clusters it (colors correspond to the clusters). Removal of these sense labels produces overlapping clusters. In Table 3, we compare directly to very similar community detection approaches, such as Chinese Whispers, MCL and Clique Percolation Method.

We found this algorithm to be useful in other scenarios, such as semantic frame induction. You can try our Java implementation to confirm my description: https://github.com/nlpub/watset-java, it is very simple to use both with CLI and API.