# Current Slide

Small screen detected. You are viewing the mobile version of SlideWiki. If you wish to edit slides you will need to use a larger device.

### Graph Clustering: Sparsest Cut

- G = (V,E). The
*cut set*of a cut is the set of edges {(u, v) ∈ E | u ∈ S, v ∈ T } and S and T are in two partitions

*Size*of the cut: # of edges in the cut set- Min-cut (e.g., C1) is not a good partition
- A better measure:
**Sparsity**:

φ=the size of the cut / min{|S|,|T|}

- A cut is
*sparsest*if its sparsity is not greater than that of any other cut - Ex. Cut C2 = ({a, b, c, d, e, f, l}, {g, h, i, j, k}) is the sparsest cut
- For k clusters, the
**modularity**o a clustering assesses the quality of the clustering:

\[Q=\sum_{i=1}^{k}(\frac{l_{i}}{|E|}-(\frac{d_{i}}{2|E|})^{2})\]

*li*: # edges between vertices in the i-th cluster

*di*: 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

**Speaker notes:**

## Content Tools

Tools

Sources (0)

Tags (0)

Comments (0)

History

Usage

Questions (0)

Playlists (0)

Quality

### Sources

There are currently no sources for this slide.