Graph Partitioning - Harding University

Intro to Web Science Harding University This work is licensed under Creative Commons Attribution-NonCommercial 3.0 Slides use figures from Ch 3.6 of Networks, Crowds and Markets by Easley & Kleinberg (2010) http://www.cs.cornell.edu/home/kleinber/networks-book/ Co-authorship network How can the tightly clustered groups be identified? Newmam & Girvan, 2004 Karate Club splits after a dispute. Can new clubs be identified based on network structure? Zachary, 1977 Graph Partitioning • Methods to break a network into sets of connected components called regions • Many general approaches – Divisive methods: Repeatedly identify and remove edges connecting densely connected regions – Agglomerative methods: Repeatedly identify and merge nodes that likely belong in the same region 7 8 3 2 1 11

9 10 6 4 5 13 12 14 Divisive Methods 7 8 3 2 1 11 9 10 6 4 5 13 12 14 Agglomerative Methods Girvan-Newman Algorithm • Divisive method Proposed by Girvan and Newman in 2002 • Uses edge betweenness to identify edges to remove • Edge betweenness: Total amount of “flow” an edge carries between all pairs of nodes where a single unit of flow between two nodes divides itself evenly among all shortest paths between the nodes (1/k units flow along each of k shortest paths) 7 8 3 2 1 11 9 10 6 4 5 13 12 14 Edge Betweenness Example Calculate total flow over edge 7-8 7 8 3 2 1 11 9 10 6 4 5 13 12 14 One unit flows over 7-8 to get from 1 to 8 7 8 3 2 1 11 9 10 6 4 5 13 12 14 One unit flows over 7-8 to get from 1 to 9 7 8 3 2 1 11 9 10 6 4 5 13 12 14 One unit flows over 7-8 to get from 1 to 10 7 8 3 2 1 11 9 10 6 4 5 13 12 14 7 total units flow over 7-8 to get from 1 to nodes 8-14 7 8 3 2 1 11 9 10 6 4 5 13 12 14 7 total units flow over 7-8 to get from 2 to nodes 8-14 7 8 3 2 1 11 9 10 6 4 5 13 12 14 7 total units flow over 7-8 to get from 3 to nodes 8-14 7 8 3 2 1 11 9 10 6 4 5 13 12 14 7 x 7 = 49 total units flow over 7-8 from nodes 1-7 to 8-14 7 8 3 2 1 11 9 10 6 4 5 13 12 14 Edge betweenness = 49 7 8 3 2 1 11 9 10 6 4 5 13 12 14 Calculate betweenness for edge 3-7 7 8 3 2 1 11 9 10 6 4 5 13 12 14 3 units flow from 1-3 to each 4-14 node, so total = 3 x 11 = 33 7 8 3 2 1 11 9 10 6 4 5 13 12 14 Betweenness = 33 for each symmetric edge 33 33 33 33 7 8 3 2 1 11 9 10 6...

Website: www.harding.edu | Filesize: -
No of Page(s): 50
Download N - Harding University.pdf