“expected” number of edges between two vertices?

Overview of past work on community structure. • How to determine the “best” number of communities. • Fast linear algebra based method. • Bringing in statistics. A Brief History of Methods • Spectral methods, graph partitioning problems. • A well known example is spectral bisection, which uses the graph/ network Laplacian. • In the special case of a network having only two communities, Fiedler proposed a method for identifying the the members nodes. L ij = δ ij k i − A ij A Brief History of Methods • Hierarchical clustering: groups nodes into communities such

that nodes within a community are similar to each other in some sense; widely used in sociology. • Technique 1) calculate a weight, for every pair of nodes in the network 2) then take the nodes with no edges between them an add edges between pairs one by one in order of their weights, from strongest to weakest. • Many ways exist for calculating the values. • The entire process is frequently represented as a dendrogram, a visualization of the vertices coalescing into communities. W ij n W ij A Brief History of Methods • Girvan-Newman Algorithm: a divisive method for determining community structure that focuses on the betweenness of edges. • Edge betweenness: the number of shortest paths between pairs of vertices that run along an edge. • Removing edges of high betweenness breaks up the connected network into communities. GN Algorithm Algorithm 1. Calculate the betweenness for all edges in the network. 2. Remove the edge with the highest betweenness. 3. Recalculate betweenness for all edges affected by the removal. 4. Repeat from steps 2 until no edges remain. M. Girvan and M.E.J. Newman, “Community structure in social and biological networks” Proc. Natl. Acad. Sci. USA 99, 7821–7826 (2002). GN Algorithm GN Algorithm The classic “Karate Club” example Modularity • Introduced by Newman and Girvan to quantify which division of a network into communities/groups was the best. • Related to Newman’s work on assortativity in networks, “Mixing patterns in networks” Phys. Rev. E 67, 026126 (2003) • Modularity: the fraction of edges falling within communities minus the expected fraction of such edges. the fraction of all edges in the network that link vertices in community i to vertices in community j. e ij : a i = summationdisplay j e ij the fraction of edges that connect to vertices in community i. Q = summationdisplay i (e ii − a 2 i ) = T re − || e 2 || M.E.J. Newman and M. Girvan, “Finding and evaluating community structure in networks” Phys. Rev. E 69, 026113 (2004) Modularity M.E.J. Newman and M. Girvan, “Finding and evaluating community structure in networks” Phys. Rev. E 69, 026113 (2004) Again the “Karate Club” Modularity 0 0.1 0.2 0.3 0.4 0.5 modularity We love to study ourselves . . . A New-New Approach - Newman later returned to the subject of community structure and modularity with a new-new approach. -...

Website: mae.ucdavis.edu | Filesize: -
No of Page(s): 36
Download “expected” number of edges between two vertices?.pdf