Data Mining_ Concepts and Techniques - Jiawei Han [319]
To find clusters in a graph, imagine cutting the graph into pieces, each piece being a cluster, such that the vertices within a cluster are well connected and the vertices in different clusters are connected in a much weaker way. Formally, for a graph, , a cut, , is a partitioning of the set of vertices V in G, that is, and . The cut set of a cut is the set of edges, . The size of the cut is the number of edges in the cut set. For weighted graphs, the size of a cut is the sum of the weights of the edges in the cut set.
“What kinds of cuts are good for deriving clusters in graphs?” In graph theory and some network applications, a minimum cut is of importance. A cut is minimum if the cut's size is not greater than any other cut's size. There are polynomial time algorithms to compute minimum cuts of graphs. Can we use these algorithms in graph clustering?
Cuts and clusters
Consider graph G in Figure 11.14. The graph has two clusters: and , and one outlier vertex, l.
Consider cut . Only one edge, namely, (e, l), crosses the two partitions created by C1. Therefore, the cut set of C1 is and the size of C1 is 1. (Note that the size of any cut in a connected graph cannot be smaller than 1.) As a minimum cut, C1 does not lead to a good clustering because it only separates the outlier vertex, l, from the rest of the graph.
Figure 11.14 A graph G and two cuts.
Cut leads to a much better clustering than C1.
The edges in the cut set of C2 are those connecting the two “natural clusters” in the graph. Specifically, for edges (d, h) and (e, k) that are in the cut set, most of the edges connecting d, h, e, and k belong to one cluster.
Example 11.21 indicates that using a minimum cut is unlikely to lead to a good clustering. We are better off choosing a cut where, for each vertex u that is involved in an edge in the cut set, most of the edges connecting to u belong to one cluster. Formally, let be the degree of u, that is, the number of edges connecting to u. The sparsity of a cut is defined as
(11.38)
A cut is sparsest if its sparsity is not greater than the sparsity of any other cut. There may be more than one sparsest cut.
In Example 11.21 and Figure 11.14, C2 is a sparsest cut. Using sparsity as the objective function, a sparsest cut tries to minimize the number of edges crossing the partitions and balance the partitions in size.
Consider a clustering on a graph that partitions the graph into k clusters. The modularity of a clustering assesses the quality of the clustering and is defined as
(11.39)
where li is the number of edges between vertices in the i th cluster, and di is the sum of the degrees of the vertices in the i th cluster. The modularity of a clustering of a graph is the difference between the fraction of all edges that fall into individual clusters and the fraction that would do so if the graph vertices were randomly connected. The optimal clustering of graphs maximizes the modularity.
Theoretically, many graph clustering problems can be regarded as finding good cuts, such as the sparsest cuts, on the graph. In practice, however, a number of challenges exist:
■ High computational cost: Many graph cut problems are computationally expensive. The sparsest cut problem, for example, is NP-hard. Therefore, finding the optimal solutions on large graphs is often impossible. A good trade-off between efficiency/scalability and quality has to be achieved.
■ Sophisticated graphs: Graphs can be more sophisticated than the ones described here, involving weights and/or cycles.
■ High dimensionality: A graph can have many vertices. In a similarity matrix, a vertex is represented as a vector (a row in the matrix) with a dimensionality that is the number of vertices in the graph. Therefore, graph clustering methods must handle high dimensionality.
■ Sparsity: A large graph is often sparse, meaning each vertex on average connects to only a small number of other vertices. A similarity