Here are some references we'll cover on part of speech tagging (POS tagging).
The last paper in this sequence refers to a graph-based clustering technique called "Chinese Whisper". I thought you might be interested in clustering on graphs. Here's a reference:
This last paper comes from Professor Manning at Stanford NLP. It reports status of POS tagging as of 2011. He points out some of the issues that make progress difficult.
CICLing2011-manning-tagging.pdf