The standard method probably involves using the methods exported by Graph and it's child modules. It is a remarkably complete suite of graph packages (Graph::Undirected in particular).

Despite numerous re-readings, I'm not sure I understand how you wish to cluster them. If I understand the question, you wish to group neighbors into clusters without disconnecting the graph? You can try removing things and use the is_connected method to see if you broke it.

UPDATE: I deleted some of this post because I think blokhead "solved" the question 100% ... a few posts down from here.