BioLayout is a powerful 3D graph visualization and analysis Java application, allowing interaction with large graphs in 3-dimensional layouts. It can handle graphs with up to and over 10,000 nodes, has many modes of operations and supports many graph queries and analysis modes. BioLayout has a facility to cluster the graph using mcl (the implementation available from this page). The resulting cluster structure is interpreted as a native class attribute and displayed by assigning colours to (the nodes in) clusters.
Rob Gevers has written an R interface to mcl. It requires you have installed the mcl software available from this page.
OpenBSD mcl package created by Andreas Kähäri. (I am not sure if the given URL is the best available link, but openBSD people surely know their way around).