This isn't a Perl solution, but if you are primarily interested in identifying clusters in your graph, you might consider using a network analysis tool, like
UCINET which does cluster analysis. It depends on what you mean by large (do you have over 200 nodes in your graph?) UCINET and many of the other tools I'm aware of have limitations as to the size of the graph they can analyze.
split//,q{john hurl, pest caretaker}and(map{print @_[$_]}(join(q{},map
+{sprintf(qq{%010u},$_)}(2**2*307*4993,5*101*641*5261,7*59*79*36997,13
+*17*71*45131,3**2*67*89*167*181))=~/\d{2}/g));