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.