  How can we find a good graph clustering of a real-world network, that allows
insight into its underlying structure and also potential functions? In this
paper, we introduce a new graph clustering algorithm Dcut from a density point
of view. The basic idea is to envision the graph clustering as a density-cut
problem, such that the vertices in the same cluster are densely connected and
the vertices between clusters are sparsely connected. To identify meaningful
clusters (communities) in a graph, a density-connected tree is first
constructed in a local fashion. Owing to the density-connected tree, Dcut
allows partitioning a graph into multiple densely tight-knit clusters directly.
We demonstrate that our method has several attractive benefits: (a) Dcut
provides an intuitive criterion to evaluate the goodness of a graph clustering
in a more natural and precise way; (b) Built upon the density-connected tree,
Dcut allows identifying the meaningful graph clusters of densely connected
vertices efficiently; (c) The density-connected tree provides a connectivity
map of vertices in a graph from a local density perspective. We systematically
evaluate our new clustering approach on synthetic as well as real data to
demonstrate its good performance.
