Graph ClusteringWhy graph clustering is useful?• Distance matrices are graphs as useful as any other clustering• Identification of communities in social networks• Webpage clustering for better data management of web dataOutline• Min s-t cut problem• Min cut problem• Multiway cut• Minimum k-cut• Other normalized cuts and spectral graph partitioningsMin s-t cut• Weighted graph G(V,E)• An s-t cut C = (S,T) of a graph G = (V, E) is a cut partition of V into S and T such that s∈S and t∈T• Cost of a cut: Cost(C) = Σe(u,v) uЄS, v ЄTw(e)• Problem: Given G, s and t find the minimum cost s-t cutMax flow problem• Flow network– Abstraction for material flowing through the edges– G = (V,E) directed graph with no parallel edges– Two distinguished nodes: s = source, t= sink– c(e) = capacity of edge eCuts• An s-t cut is a partition (S,T) of V with sЄS and tЄT• capacity of a cut (S,T) is cap(S,T) = Σe out of Sc(e)• Find s-t cut with the minimum capacity: this problem can be solved optimally in polynomial time by using flow techniquesFlows• An s-t flow is a function that satisfies– For each eЄE 0≤f(e) ≤c(e) [capacity]– For each vЄV-{s,t}: Σe in to vf(e) = Σe out of vf(e) [conservation]• The value of a flow f is: v(f) = Σe out of s f(e)Max flow problem• Find s-t flow of maximum valueFlows and cuts• Flow value lemma: Let f be any flow and let (S,T) be any s-t cut. Then, the net flow sent across the cut is equal to the amount leaving sΣe out of Sf(e) – Σe in to Sf(e) = v(f)Flows and cuts• Weak duality: Let f be any flow and let (S,T) be any s-t cut. Then the value of the flow is at most the capacity of the cut defined by (S,T):v(f) ≤cap(S,T)Certificate of optimality• Let f be any flow and let (S,T) be any cut. If v(f)= cap(S,T) then f is a max flow and (S,T) is a min cut.• The min-cut max-flow problems can be solved optimally in polynomial time!Setting• Connected, undirected graph G=(V,E)• Assignment of weights to edges: w: ER+• Cut: Partition of V into two sets: V’, V-V’. The set of edges with one end point in V and the other in V’ define the cut• The removal of the cut disconnects G• Cost of a cut: sum of the weights of the edges that have one of their end point in V’ and the other in V-V’Min cut problem• Can we solve the min-cut problem using an algorithm for s-t cut?Randomized min-cut algorithm• Repeat : pick an edge uniformly at random and merge the two vertices at its end-points– If as a result there are several edges between some pairs of (newly-formed) vertices retain them all– Edges between vertices that are merged are removed (no self-loops)• Until only two vertices remain• The set of edges between these two vertices is a cut in Gand is output as a candidate min-cutExample of contractioneObservations on the algorithm• Every cut in the graph at any intermediate stage is a cut in the original graphAnalysis of the algorithm• C the min-cut of size k G has at least kn/2 edges– Why?• Ei: the event of not picking an edge of C at the i-th step for 1≤i ≤n-2• Step 1:– Probability that the edge randomly chosen is in C is at most 2k/(kn)=2/n Pr(E1) ≥ 1-2/n• Step 2:– If E1occurs, then there are at least n(n-1)/2 edges remaining– The probability of picking one from C is at most 2/(n-1) Pr(E2|E1) = 1 – 2/(n-1)• Step i:– Number of remaining vertices: n-i+1– Number of remaining edges: k(n-i+1)/2 (since we never picked an edge from the cut)– Pr(Ei|Πj=1…i-1Ej) ≥ 1 – 2/(n-i+1)– Probability that no edge in C is ever picked: Pr(Πi=1…n-2Ei) ≥ Πi=1…n-2(1-2/(n-i+1))=2/(n2-n)• The probability of discovering a particular min-cut is larger than 2/n2• Repeat the above algorithm n2/2 times. The probability that a min-cut is not found is (1-2/n2)n^2/2 < 1/eMultiway cut (analogue of s-t cut)• Problem: Given a set of terminals S = {s1,…,sk} subset of V, a multiway cut is a set of edges whose removal disconnects the terminals from each other. The multiway cut problem asks for the minimum weight such set.• The multiway cut problem is NP-hard (for k>2)Algorithm for multiway cut• For each i=1,…,k, compute the minimum weight isolating cut for si, say Ci• Discard the heaviest of these cuts and output the union of the rest, say C• Isolating cut for si: The set of edges whose removal disconnects sifrom the rest of the terminals• How can we find a minimum-weight isolating cut?– Can we do it with a single s-t cut computation?Approximation result• The previous algorithm achieves an approximation guarantee of 2-2/k• ProofMinimum k-cut • A set of edges whose removal leaves k connected components is called a k-cut. The minimum k-cut problem asks for a minimum-weight k-cut• Recursively compute cuts in G (and the resulting connected components) until there are kcomponents left• This is a (2-2/k)-approximation algorithmMinimum k-cut algorithm• Compute the Gomory-Hu tree T for G• Output the union of the lightest k-1 cuts of the n-1 cuts associated with edges of T in G; let C be this union• The above algorithm is a (2-2/k)-approximation algorithmGomory-Hu Tree• T is a tree with vertex set V• The edges of T need not be in E• Let e be an edge in T; its removal from T creates two connected components with vertex sets (S,S’)• The cut in G defined by partition (S,S’) is the cut associated with e in GGomory-Hu tree• Tree T is said to be the Gomory-Hu tree for Gif– For each pair of vertices u,v in V, the weight of a minimum u-v cut in G is the same as that in T– For each edge e in T, w’(e) is the weight of the cut associated with e in GMin-cuts again• What does it mean that a set of nodes are well or sparsely interconnected?• min-cut: the min number of edges such that when removed cause the graph to become disconnected– small min-cut implies sparse connectivity–UV-UUi UVjUji,AUVU,E minMeasuring connectivity• What does it mean that a set of nodes are well interconnected?• min-cut: the min number of edges such that when removed cause the graph to become disconnected– not always a good idea!UUV-UV-UGraph expansion• Normalize the cut by the size of the smallest component• Cut ratio:• Graph expansion:• We will now see how the graph expansion relates to the eigenvalue of the adjacency matrix AUV,UminU-VU,EminGαUUV,UminU-VU,EαSpectral analysis• The Laplacian matrix L = D – A where–
View Full Document
Unlocking...