Compare the SCAN algorithm (Section 9.5.3) with DBSCAN (Section 8.4.1). What are their similarities and differences? 9.5.3

Compare the SCAN algorithm (Section 9.5.3) with DBSCAN (Section 8.4.1). What are their similarities and differences?

Transcribed Image Text:

9.5.3 Graph clustering methods Let us consider how to conduct clustering on a graph. We first describe the intuition behind graph clustering. We then discuss two general categories of graph clustering methods. The intuition of finding clusters in a graph is to cut 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, G = (V, E), a cut, C = (S, T), is a partitioning of the set of vertices V in G, that is, V=SUT and SnT = . The cut set of a cut is the set of edges, {(u, v) E Elu ES, v E T}. 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 size of the cut is not greater than the size of any other cut. There are polynomial time algorithms to compute minimum cuts of graphs. Can we use those algorithms in graph clustering? Example 9.19. Cuts and clusters. Consider graph G in Fig. 9.17. The graph has two clusters: (a, b, c, d, e, f) and {g, h, i, j, k), and one outlier vertex, 1. Consider cut C = ({a, b, c, d, e, f, g, h, i, j, k}, {}). Only one edge, namely, (e, 1), crosses the two partitions created by C. Therefore the cut set of C is {(e,1)), and the size of C is 1. (Note that the size of any cut in a connected graph cannot be smaller than 1.) As a minimum cut, C does not lead to a good clustering because it only separates the outlier vertex, 1, from the rest of the graph. Cut C = ({a, b, c, d, e, f,l}, {g, h, i, j, k}) leads to a much better clustering than C. The edges in the cut set of C 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.