Graph clustering

COMPUTATIONAL STATISTICS

1. GRAPH CLUSTERING Prepared By Ms.W.Ancy Breen,A.P /CSE SRMIST

2. Graph clustering Graph clustering is an important subject, and deals with clustering with graphs. The data of a clustering problem can be represented as a graph where each element to be clustered is represented as a node and the distance between two elements is modelled by a certain weight on the edge linking the nodes. Thus in graph clustering, elements within a cluster are connected to each other but have no connection to elements outside that cluster.   Structure of a cluster Advantages: The clustering concept is very useful in various fields of computer science such as image segmentation and complex network analysis. In biology and medicine, the clustering concept is also frequently used to analyze data; for example, in the fields of gene expression and protein structure analysis. The clustering concept is also used in astronomy.

3. Cont... Types Between-graph Clustering a set of graphs Within-graph Clustering the nodes/edges of a single graph Between-graph clustering methods divide a set of graphs into different clusters E.g., A set of graphs representing chemical compounds can be grouped into clusters based on their structural similarity. Within-graph clustering methods divides the nodes of a graph into clusters E.g., In a social networking graph, these clusters could represent people with same/similar hobbies

4. Graph Clustering-Algorithms Algorithms for Within Graph Clustering k-Spanning Tree(Minimal spanning tree) Shared Nearest Neighbor Betweenness Centrality Based Highly Connected Components Maximal Clique Enumeration

5. k -Spanning Tree 5 1 2 3 4 5 2 3 2 k-Spanning Tree k k groups of non-overlapping vertices 4 Minimum Spanning Tree STEPS: Obtains the Minimum Spanning Tree (MST) of i nput g raph G Removes k-1 edges from the MST Results in k clusters

6. What is a Spanning Tree? A connected subgraph with no cycles that includes all vertices in the graph. 6 1 2 3 4 5 2 3 2 4 6 5 7 4 1 2 3 4 5 2 6 7 Weight = 17 2 Note: Weight can represent either distance or similarity between two vertices or similarity of the two vertices G

7. What is a Minimum Spanning Tree (MST)? 7 1 2 3 4 5 2 3 2 4 6 5 7 4 G 1 2 3 4 5 2 3 2 4 Weight = 11 2 1 2 3 4 5 2 4 5 Weight = 13 1 2 3 4 5 2 6 7 Weight = 17 2 Minimal Spanning Tree: A minimal spanning tree of a connected graph G=(V,E) is a connected subgraph with minimal weight that contains all nodes of G and has no cyces . The spanning tree of a graph with the minimum possible sum of edge weights, if the edge weights represent distance Note: maximum possible sum of edge weights, if the edge weights represent similarity

8. k -Spanning Tree 8 1 2 3 4 5 2 3 2 Remove k-1 edges with highest weight 4 Minimum Spanning Tree Note: k – is the number of clusters E.g., k=3 1 2 3 4 5 2 3 2 4 E.g., k=3 1 2 3 4 5 3 Clusters

9. 9 Shared Nearest Neighbor Clustering 1 2 3 4 Shared Nearest Neighbor Graph (SNN) 2 2 2 2 1 1 3 2 Shared Nearest Neighbor Clustering Groups of non-overlapping vertices STEPS: Obtains the Shared Nearest Neighbor Graph (SNN) of i nput g raph G Removes edges from the SNN with weight less than τ τ

10. What is Shared Nearest Neighbor? 10 u v   Shared Nearest Neighbor is a proximity measure and denotes the number of neighbor nodes common between any given pair of nodes

11. Shared Nearest Neighbor (SNN) Graph 11 1 2 3 4 G 1 2 3 4 SNN 2 2 2 2 1 1 3 Given input graph G, weight each edge ( u,v ) with the number of shared nearest neighbors between u and v 1 Node 0 and Node 1 have 2 neighbors in common: Node 2 and Node 3

12. Shared Nearest Neighbor Clustering Jarvis-Patrick Algorithm 12 1 2 3 4 SNN g raph of input graph G 2 2 2 2 1 1 3 2 If u and v share more than τ neighbors Place them in the same cluster 1 2 3 4 E.g., τ =3

13. What is Betweenness Centrality? Two types: Vertex Betweenness Edge Betweenness 13 Betweenness centrality quantifies the degree to which a vertex (or edge) occurs on the shortest path between all the other pairs of nodes

14. Vertex Betweenness 14 The number of shortest paths in the graph G that pass through a given node S G E.g., Sharon is likely a liaison between NCSU and DUKE and hence many connections between DUKE and NCSU pass through Sharon

15. Edge Betweenness The number of shortest paths in the graph G that pass through given edge (S, B) 15 E.g., Sharon and Bob both study at NCSU and they are the only link between NY DANCE and CISCO groups NCSU Vertices and Edges with high Betweenness form good starting points to identify clusters

16. Vertex Betweenness Clustering 16 Repeat until h ighest vertex b etweenness ≤ μ Select vertex v with the h ighest b etweenness E.g., Vertex 3 with value 0.67 Given Input graph G Betweenness for each vertex 1. Disconnect graph at selected vertex (e.g., vertex 3 ) 2. Copy v ertex to both Components

17. 17 Edge-Betweenness Clustering Girvan and Newman Algorithm 17 Repeat until h ighest e dge b etweenness ≤ μ Select edge with Highest Betweenness E.g., edge (3,4) with value 0.571 Given Input Graph G Betweenness for each edge Disconnect graph at selected edge (E.g., (3,4 ))

18. What is a Highly Connected Subgraph? Requires the following definitions Cut Minimum Edge Cut ( MinCut ) Edge Connectivity (EC) 18

19. Cut The set of edges whose removal disconnects a graph 19 6 5 4 7 3 2 1 8 6 5 4 7 3 2 1 8 6 5 4 7 3 2 1 8 Cut = {(0,1),(1,2),(1,3} Cut = {(3,5),(4,2)}

20. Minimum Cut 20 6 5 4 7 3 2 1 8 6 5 4 7 3 2 1 8 MinCut = {(3,5),(4,2)} The minimum set of edges whose removal disconnects a graph

21. Edge Connectivity (EC) Minimum NUMBER of edges that will disconnect a graph 21 6 5 4 7 3 2 1 8 MinCut = {(3,5),(4,2)} EC = | MinCut | = | {(3,5),(4,2 )}| = 2 Edge C onnectivity

22. Highly Connected Subgraph (HCS) A graph G =(V,E) is highly connected if EC(G)>V/2 22 6 5 4 7 3 2 1 8 EC(G) > V/2 2 > 9/2 G G is NOT a highly connected subgraph

23. HCS Clustering 23 6 5 4 7 3 2 1 8 Find the Minimum Cut MinCut (G) Given Input graph G (3,5 ),(4,2)} YES Return G NO 3 2 1 6 5 4 7 8 G1 G2 Divide G using MinCut Is EC(G)> V/2 Process Graph G1 Process Graph G2

24. What is a Clique? A subgraph C of graph G with edges between all pairs of nodes 24 6 5 4 7 8 Clique 6 5 7 G C

25. What is a Maximal Clique? 25 6 5 4 7 8 Clique Maximal Clique 6 5 7 6 5 7 8 A maximal clique is a clique that is not part of a larger clique.