{"algorithm":"girvan-newman","about":["Girvan-Newman finds communities by taking a graph apart. The few edges between two tight groups carry many shortest paths, because every route from one group to the other has to cross them. The algorithm counts how many shortest paths between pairs of vertices use each edge, the edge's betweenness. It removes the edge with the highest count, then counts again.","It stops once the graph has fallen into k connected components, and those are the communities. gograph counts with Brandes' method, a breadth-first search from every vertex, so the length of a path is its number of edges and weights aren't used. That costs O(V·(V+E)) for each edge it removes, and O(E·V·(V+E)) in the worst case. When edges tie, it removes the first one in the graph's edge order, so every run gives the same result. Scores within one part in a billion of the highest count as tied, since the same paths added up in another order can round differently.","It is slow on large graphs, but each split has a clear reason: it removes the link that the most routes cross. A directed graph splits as if it were undirected, and each community keeps the direction of its edges. It works on a copy, so the input stays as it was. Each community it returns keeps all of its edges, including the ones removed along the way."],"template":{"id":"campus-network","name":"Campus network","description":"A hundred switches, servers and computers in ten buildings of a university campus, A to J. Each id is a building letter and a number, so D7 is number 7 in building D. A is the data center, where the core switches A1 and A2 link to the main switch of every other building, always number 1. The larger buildings have more switches between the main switch and the computers, and two pairs of neighboring buildings also have a direct link.","family":"undirected","directed":false,"weighted":false,"acyclic":false,"vertices":[{"id":"A1","x":522,"y":486},{"id":"A2","x":511,"y":541},{"id":"A3","x":472,"y":470},{"id":"A4","x":566,"y":503},{"id":"A5","x":459,"y":548},{"id":"A6","x":515,"y":431},{"id":"A7","x":556,"y":566},{"id":"A8","x":424,"y":488},{"id":"A9","x":585,"y":455},{"id":"A10","x":483,"y":596},{"id":"A11","x":462,"y":414},{"id":"A12","x":607,"y":540},{"id":"A13","x":406,"y":545},{"id":"A14","x":557,"y":400},{"id":"A15","x":543,"y":616},{"id":"A16","x":402,"y":442},{"id":"B1","x":289,"y":814},{"id":"B2","x":278,"y":869},{"id":"B3","x":240,"y":797},{"id":"B4","x":334,"y":833},{"id":"B5","x":225,"y":874},{"id":"B6","x":284,"y":759},{"id":"B7","x":322,"y":895},{"id":"B8","x":192,"y":814},{"id":"B9","x":354,"y":785},{"id":"B10","x":248,"y":923},{"id":"B11","x":232,"y":740},{"id":"B12","x":373,"y":870},{"id":"B13","x":173,"y":870},{"id":"B14","x":327,"y":729},{"id":"C1","x":133,"y":571},{"id":"C2","x":105,"y":620},{"id":"C3","x":91,"y":540},{"id":"C4","x":169,"y":602},{"id":"C5","x":54,"y":609},{"id":"C6","x":144,"y":517},{"id":"C7","x":139,"y":658},{"id":"C8","x":40,"y":541},{"id":"D1","x":166,"y":321},{"id":"D2","x":131,"y":277},{"id":"D3","x":211,"y":294},{"id":"D4","x":123,"y":343},{"id":"D5","x":160,"y":234},{"id":"D6","x":212,"y":352},{"id":"D7","x":82,"y":294},{"id":"D8","x":228,"y":246},{"id":"D9","x":148,"y":389},{"id":"D10","x":108,"y":220},{"id":"D11","x":259,"y":324},{"id":"D12","x":69,"y":350},{"id":"E1","x":415,"y":105},{"id":"E2","x":387,"y":154},{"id":"E3","x":373,"y":74},{"id":"E4","x":451,"y":137},{"id":"E5","x":336,"y":143},{"id":"E6","x":427,"y":51},{"id":"E7","x":421,"y":193},{"id":"E8","x":322,"y":75},{"id":"E9","x":485,"y":97},{"id":"E10","x":342,"y":196},{"id":"F1","x":672,"y":160},{"id":"F2","x":677,"y":104},{"id":"F3","x":723,"y":172},{"id":"F4","x":626,"y":147},{"id":"F5","x":728,"y":93},{"id":"F6","x":684,"y":215},{"id":"F7","x":630,"y":83},{"id":"F8","x":769,"y":149},{"id":"F9","x":612,"y":197},{"id":"F10","x":700,"y":47},{"id":"G1","x":856,"y":351},{"id":"G2","x":892,"y":307},{"id":"G3","x":892,"y":389},{"id":"G4","x":826,"y":314},{"id":"G5","x":941,"y":327},{"id":"G6","x":836,"y":403},{"id":"G7","x":865,"y":264},{"id":"G8","x":943,"y":396},{"id":"H1","x":873,"y":621},{"id":"H2","x":914,"y":582},{"id":"H3","x":904,"y":663},{"id":"H4","x":848,"y":580},{"id":"H5","x":960,"y":608},{"id":"H6","x":846,"y":669},{"id":"H7","x":893,"y":536},{"id":"H8","x":953,"y":677},{"id":"H9","x":804,"y":608},{"id":"I1","x":754,"y":816},{"id":"I2","x":739,"y":871},{"id":"I3","x":706,"y":796},{"id":"I4","x":797,"y":838},{"id":"I5","x":686,"y":872},{"id":"I6","x":752,"y":761},{"id":"I7","x":781,"y":900},{"id":"J1","x":564,"y":877},{"id":"J2","x":569,"y":925},{"id":"J3","x":530,"y":953},{"id":"J4","x":486,"y":933},{"id":"J5","x":481,"y":885},{"id":"J6","x":520,"y":857}],"edges":[{"from":"A1","to":"A2"},{"from":"A1","to":"A3"},{"from":"A1","to":"A4"},{"from":"A2","to":"A3"},{"from":"A2","to":"A4"},{"from":"A3","to":"A5"},{"from":"A3","to":"A6"},{"from":"A3","to":"A7"},{"from":"A3","to":"A8"},{"from":"A3","to":"A9"},{"from":"A3","to":"A10"},{"from":"A4","to":"A11"},{"from":"A4","to":"A12"},{"from":"A4","to":"A13"},{"from":"A4","to":"A14"},{"from":"A4","to":"A15"},{"from":"A4","to":"A16"},{"from":"B1","to":"A1"},{"from":"B1","to":"A2"},{"from":"C1","to":"A1"},{"from":"C1","to":"A2"},{"from":"D1","to":"A1"},{"from":"D1","to":"A2"},{"from":"E1","to":"A1"},{"from":"E1","to":"A2"},{"from":"F1","to":"A1"},{"from":"F1","to":"A2"},{"from":"G1","to":"A1"},{"from":"G1","to":"A2"},{"from":"H1","to":"A1"},{"from":"H1","to":"A2"},{"from":"I1","to":"A1"},{"from":"I1","to":"A2"},{"from":"J1","to":"A1"},{"from":"J1","to":"A2"},{"from":"C1","to":"D1"},{"from":"H1","to":"I1"},{"from":"B1","to":"B2"},{"from":"B1","to":"B3"},{"from":"B2","to":"B3"},{"from":"B2","to":"B4"},{"from":"B2","to":"B5"},{"from":"B2","to":"B6"},{"from":"B2","to":"B7"},{"from":"B2","to":"B8"},{"from":"B3","to":"B9"},{"from":"B3","to":"B10"},{"from":"B3","to":"B11"},{"from":"B3","to":"B12"},{"from":"B3","to":"B13"},{"from":"B3","to":"B14"},{"from":"C1","to":"C2"},{"from":"C1","to":"C3"},{"from":"C1","to":"C4"},{"from":"C1","to":"C5"},{"from":"C1","to":"C6"},{"from":"C1","to":"C7"},{"from":"C1","to":"C8"},{"from":"D1","to":"D2"},{"from":"D1","to":"D3"},{"from":"D2","to":"D3"},{"from":"D2","to":"D4"},{"from":"D2","to":"D5"},{"from":"D2","to":"D6"},{"from":"D2","to":"D7"},{"from":"D3","to":"D8"},{"from":"D3","to":"D9"},{"from":"D3","to":"D10"},{"from":"D3","to":"D11"},{"from":"D3","to":"D12"},{"from":"E1","to":"E2"},{"from":"E1","to":"E3"},{"from":"E1","to":"E4"},{"from":"E1","to":"E5"},{"from":"E2","to":"E6"},{"from":"E2","to":"E7"},{"from":"E2","to":"E8"},{"from":"E2","to":"E9"},{"from":"E2","to":"E10"},{"from":"F1","to":"F2"},{"from":"F1","to":"F3"},{"from":"F1","to":"F4"},{"from":"F1","to":"F5"},{"from":"F2","to":"F6"},{"from":"F2","to":"F7"},{"from":"F2","to":"F8"},{"from":"F2","to":"F9"},{"from":"F2","to":"F10"},{"from":"G1","to":"G2"},{"from":"G1","to":"G3"},{"from":"G1","to":"G4"},{"from":"G1","to":"G5"},{"from":"G1","to":"G6"},{"from":"G1","to":"G7"},{"from":"G1","to":"G8"},{"from":"H1","to":"H2"},{"from":"H1","to":"H3"},{"from":"H1","to":"H4"},{"from":"H1","to":"H5"},{"from":"H2","to":"H6"},{"from":"H2","to":"H7"},{"from":"H2","to":"H8"},{"from":"H2","to":"H9"},{"from":"I1","to":"I2"},{"from":"I1","to":"I3"},{"from":"I1","to":"I4"},{"from":"I1","to":"I5"},{"from":"I1","to":"I6"},{"from":"I1","to":"I7"},{"from":"J1","to":"J2"},{"from":"J1","to":"J3"},{"from":"J1","to":"J4"},{"from":"J1","to":"J5"},{"from":"J1","to":"J6"}],"details":{"vertices":100,"edges":114,"directed":false,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.02303030303030303,"degree":{"min":1,"avg":2.28,"max":12},"selfLoops":0,"components":1}},"problem":"Split the campus network into 8 parts along the links that the most routes between devices cross.","params":{"k":8},"result":{"kind":"sets","sets":[["A1","A2","A3","A4","A5","A6","A7","A8","A9","A10","A11","A12","A13","A14","A15","A16","B1","D1","E1","E3","E4","E5","F1","F3","F4","F5","H1","H3","H4","H5","I1","I2","I3","I4","I5","I6","I7","J1","J2","J3","J4","J5","J6"],["B2","B3","B4","B5","B6","B7","B8","B9","B10","B11","B12","B13","B14"],["C1","C2","C3","C4","C5","C6","C7","C8"],["D2","D3","D4","D5","D6","D7","D8","D9","D10","D11","D12"],["E2","E6","E7","E8","E9","E10"],["F2","F6","F7","F8","F9","F10"],["G1","G2","G3","G4","G5","G6","G7","G8"],["H2","H6","H7","H8","H9"]]},"answer":"The 8 communities have 43, 13, 8, 11, 6, 6, 8 and 5 vertices: A1, A2, A3, A4, A5, A6, A7, A8, A9, A10 and 33 more; B2, B3, B4, B5, B6, B7, B8, B9, B10, B11 and 3 more; C1, C2, C3, C4, C5, C6, C7 and C8; D2, D3, D4, D5, D6, D7, D8, D9, D10, D11 and 1 more; E2, E6, E7, E8, E9 and E10; F2, F6, F7, F8, F9 and F10; G1, G2, G3, G4, G5, G6, G7 and G8; H2, H6, H7, H8 and H9.","legend":{"vertex":[{"id":"idle","label":"Vertex","color":"#64748B","shape":"hollow"},{"id":"current","label":"End of the removed edge","color":"#56B4E9","shape":"ring"}],"edge":[{"id":"idle","label":"Edge","color":"#475569","shape":"line"},{"id":"removed","label":"Removed","color":"#CC79A7","shape":"dashed"}],"panels":[{"id":"betweenness","title":"Highest betweenness","kind":"table"},{"id":"communities","title":"Communities","kind":"groups"}]},"steps":[{"say":"Girvan-Newman removes edges one at a time until the graph falls apart into k = 8 communities. Before each removal it scores every edge by its betweenness: the number of shortest paths between pairs of vertices that cross it, with tied shortest paths sharing the credit. Then it removes the edge with the highest score. The graph starts as one community.","ops":[{"panel":"communities","groups":[["A1","A2","A3","A4","A5","A6","A7","A8","A9","A10","A11","A12","A13","A14","A15","A16","B1","B2","B3","B4","B5","B6","B7","B8","B9","B10","B11","B12","B13","B14","C1","C2","C3","C4","C5","C6","C7","C8","D1","D2","D3","D4","D5","D6","D7","D8","D9","D10","D11","D12","E1","E2","E3","E4","E5","E6","E7","E8","E9","E10","F1","F2","F3","F4","F5","F6","F7","F8","F9","F10","G1","G2","G3","G4","G5","G6","G7","G8","H1","H2","H3","H4","H5","H6","H7","H8","H9","I1","I2","I3","I4","I5","I6","I7","J1","J2","J3","J4","J5","J6"]]}]},{"say":"Remove the edge between B1 and B3. Its betweenness, 609, is the highest. The graph is still in one piece.","ops":[{"v":"B1","state":"current"},{"v":"B3","state":"current"},{"e":["B1","B3"],"state":"removed"},{"panel":"betweenness","set":{"B1 and B3":"609"}},{"panel":"betweenness","set":{"A1 and B1":"602"}},{"panel":"betweenness","set":{"A2 and B1":"602"}},{"panel":"betweenness","set":{"E1 and E2":"564"}},{"panel":"betweenness","set":{"F1 and F2":"564"}}]},{"say":"Remove the edge between B1 and B2. Its betweenness, 1131, is the highest. That splits the graph into parts of 87 and 13 vertices, so there are now 2 communities.","ops":[{"v":"B3","state":"idle"},{"v":"B1","state":"current"},{"v":"B2","state":"current"},{"e":["B1","B2"],"state":"removed"},{"panel":"betweenness","unset":["B1 and B3","A1 and B1","A2 and B1","E1 and E2","F1 and F2"]},{"panel":"betweenness","set":{"B1 and B2":"1131"}},{"panel":"betweenness","set":{"B2 and B3":"651"}},{"panel":"betweenness","set":{"A1 and B1":"602"}},{"panel":"betweenness","set":{"A2 and B1":"602"}},{"panel":"betweenness","set":{"E1 and E2":"564"}},{"panel":"communities","groups":[["A1","A2","A3","A4","A5","A6","A7","A8","A9","A10","A11","A12","A13","A14","A15","A16","B1","C1","C2","C3","C4","C5","C6","C7","C8","D1","D2","D3","D4","D5","D6","D7","D8","D9","D10","D11","D12","E1","E2","E3","E4","E5","E6","E7","E8","E9","E10","F1","F2","F3","F4","F5","F6","F7","F8","F9","F10","G1","G2","G3","G4","G5","G6","G7","G8","H1","H2","H3","H4","H5","H6","H7","H8","H9","I1","I2","I3","I4","I5","I6","I7","J1","J2","J3","J4","J5","J6"],["B2","B3","B4","B5","B6","B7","B8","B9","B10","B11","B12","B13","B14"]]}]},{"say":"Remove the edge between E1 and E2. Its betweenness, 486, ties for the highest with the edge between F1 and F2, and it comes first in gograph's AllEdges order. That splits a community of 87 into parts of 81 and 6 vertices, so there are now 3 communities.","ops":[{"v":"B1","state":"idle"},{"v":"B2","state":"idle"},{"v":"E1","state":"current"},{"v":"E2","state":"current"},{"e":["E1","E2"],"state":"removed"},{"panel":"betweenness","unset":["B1 and B2","B2 and B3","A1 and B1","A2 and B1","E1 and E2"]},{"panel":"betweenness","set":{"E1 and E2":"486"}},{"panel":"betweenness","set":{"F1 and F2":"486"}},{"panel":"betweenness","set":{"D1 and D3":"456"}},{"panel":"betweenness","set":{"H1 and H2":"410"}},{"panel":"betweenness","set":{"A1 and D1":"402"}},{"panel":"communities","groups":[["A1","A2","A3","A4","A5","A6","A7","A8","A9","A10","A11","A12","A13","A14","A15","A16","B1","C1","C2","C3","C4","C5","C6","C7","C8","D1","D2","D3","D4","D5","D6","D7","D8","D9","D10","D11","D12","E1","E3","E4","E5","F1","F2","F3","F4","F5","F6","F7","F8","F9","F10","G1","G2","G3","G4","G5","G6","G7","G8","H1","H2","H3","H4","H5","H6","H7","H8","H9","I1","I2","I3","I4","I5","I6","I7","J1","J2","J3","J4","J5","J6"],["B2","B3","B4","B5","B6","B7","B8","B9","B10","B11","B12","B13","B14"],["E2","E6","E7","E8","E9","E10"]]}]},{"say":"Remove the edge between F1 and F2. Its betweenness, 450, is the highest. That splits a community of 81 into parts of 75 and 6 vertices, so there are now 4 communities.","ops":[{"v":"E1","state":"idle"},{"v":"E2","state":"idle"},{"v":"F1","state":"current"},{"v":"F2","state":"current"},{"e":["F1","F2"],"state":"removed"},{"panel":"betweenness","unset":["E1 and E2","F1 and F2","D1 and D3","H1 and H2","A1 and D1"]},{"panel":"betweenness","set":{"F1 and F2":"450"}},{"panel":"betweenness","set":{"D1 and D3":"420"}},{"panel":"betweenness","set":{"H1 and H2":"380"}},{"panel":"betweenness","set":{"A1 and D1":"366"}},{"panel":"betweenness","set":{"A2 and D1":"366"}},{"panel":"communities","groups":[["A1","A2","A3","A4","A5","A6","A7","A8","A9","A10","A11","A12","A13","A14","A15","A16","B1","C1","C2","C3","C4","C5","C6","C7","C8","D1","D2","D3","D4","D5","D6","D7","D8","D9","D10","D11","D12","E1","E3","E4","E5","F1","F3","F4","F5","G1","G2","G3","G4","G5","G6","G7","G8","H1","H2","H3","H4","H5","H6","H7","H8","H9","I1","I2","I3","I4","I5","I6","I7","J1","J2","J3","J4","J5","J6"],["B2","B3","B4","B5","B6","B7","B8","B9","B10","B11","B12","B13","B14"],["E2","E6","E7","E8","E9","E10"],["F2","F6","F7","F8","F9","F10"]]}]},{"say":"Remove the edge between D1 and D3. Its betweenness, 384, is the highest. There are still 4 communities.","ops":[{"v":"F1","state":"idle"},{"v":"F2","state":"idle"},{"v":"D1","state":"current"},{"v":"D3","state":"current"},{"e":["D1","D3"],"state":"removed"},{"panel":"betweenness","unset":["F1 and F2","D1 and D3","H1 and H2","A1 and D1","A2 and D1"]},{"panel":"betweenness","set":{"D1 and D3":"384"}},{"panel":"betweenness","set":{"H1 and H2":"350"}},{"panel":"betweenness","set":{"A1 and D1":"330"}},{"panel":"betweenness","set":{"A2 and D1":"330"}},{"panel":"betweenness","set":{"D1 and D2":"320"}}]},{"say":"Remove the edge between D1 and D2. Its betweenness, 704, is the highest. That splits a community of 75 into parts of 64 and 11 vertices, so there are now 5 communities.","ops":[{"v":"D3","state":"idle"},{"v":"D1","state":"current"},{"v":"D2","state":"current"},{"e":["D1","D2"],"state":"removed"},{"panel":"betweenness","unset":["D1 and D3","H1 and H2","A1 and D1","A2 and D1","D1 and D2"]},{"panel":"betweenness","set":{"D1 and D2":"704"}},{"panel":"betweenness","set":{"D2 and D3":"414"}},{"panel":"betweenness","set":{"H1 and H2":"350"}},{"panel":"betweenness","set":{"A1 and D1":"330"}},{"panel":"betweenness","set":{"A2 and D1":"330"}},{"panel":"communities","groups":[["A1","A2","A3","A4","A5","A6","A7","A8","A9","A10","A11","A12","A13","A14","A15","A16","B1","C1","C2","C3","C4","C5","C6","C7","C8","D1","E1","E3","E4","E5","F1","F3","F4","F5","G1","G2","G3","G4","G5","G6","G7","G8","H1","H2","H3","H4","H5","H6","H7","H8","H9","I1","I2","I3","I4","I5","I6","I7","J1","J2","J3","J4","J5","J6"],["B2","B3","B4","B5","B6","B7","B8","B9","B10","B11","B12","B13","B14"],["D2","D3","D4","D5","D6","D7","D8","D9","D10","D11","D12"],["E2","E6","E7","E8","E9","E10"],["F2","F6","F7","F8","F9","F10"]]}]},{"say":"Remove the edge between H1 and H2. Its betweenness, 295, is the highest. H2, H6, H7, H8 and H9 split off, so there are now 6 communities.","ops":[{"v":"D1","state":"idle"},{"v":"D2","state":"idle"},{"v":"H1","state":"current"},{"v":"H2","state":"current"},{"e":["H1","H2"],"state":"removed"},{"panel":"betweenness","unset":["D1 and D2","D2 and D3","H1 and H2","A1 and D1","A2 and D1"]},{"panel":"betweenness","set":{"H1 and H2":"295"}},{"panel":"betweenness","set":{"A1 and G1":"224"}},{"panel":"betweenness","set":{"A2 and G1":"224"}},{"panel":"betweenness","set":{"A1 and C1":"220"}},{"panel":"betweenness","set":{"A2 and C1":"220"}},{"panel":"communities","groups":[["A1","A2","A3","A4","A5","A6","A7","A8","A9","A10","A11","A12","A13","A14","A15","A16","B1","C1","C2","C3","C4","C5","C6","C7","C8","D1","E1","E3","E4","E5","F1","F3","F4","F5","G1","G2","G3","G4","G5","G6","G7","G8","H1","H3","H4","H5","I1","I2","I3","I4","I5","I6","I7","J1","J2","J3","J4","J5","J6"],["B2","B3","B4","B5","B6","B7","B8","B9","B10","B11","B12","B13","B14"],["D2","D3","D4","D5","D6","D7","D8","D9","D10","D11","D12"],["E2","E6","E7","E8","E9","E10"],["F2","F6","F7","F8","F9","F10"],["H2","H6","H7","H8","H9"]]}]},{"say":"Remove the edge between A1 and G1. Its betweenness, 204, ties for the highest with the edge between A2 and G1, and it comes first in gograph's AllEdges order. There are still 6 communities.","ops":[{"v":"H1","state":"idle"},{"v":"H2","state":"idle"},{"v":"A1","state":"current"},{"v":"G1","state":"current"},{"e":["A1","G1"],"state":"removed"},{"panel":"betweenness","unset":["H1 and H2","A1 and G1","A2 and G1","A1 and C1","A2 and C1"]},{"panel":"betweenness","set":{"A1 and G1":"204"}},{"panel":"betweenness","set":{"A2 and G1":"204"}},{"panel":"betweenness","set":{"A1 and C1":"200"}},{"panel":"betweenness","set":{"A2 and C1":"200"}},{"panel":"betweenness","set":{"A1 and A3":"182"}}]},{"say":"Remove the edge between A2 and G1. Its betweenness, 408, is the highest. That splits a community of 59 into parts of 51 and 8 vertices, so there are now 7 communities.","ops":[{"v":"A1","state":"idle"},{"v":"A2","state":"current"},{"v":"G1","state":"current"},{"e":["A2","G1"],"state":"removed"},{"panel":"betweenness","unset":["A1 and G1","A2 and G1","A1 and C1","A2 and C1","A1 and A3"]},{"panel":"betweenness","set":{"A2 and G1":"408"}},{"panel":"betweenness","set":{"A2 and C1":"232"}},{"panel":"betweenness","set":{"A2 and A3":"210"}},{"panel":"betweenness","set":{"A2 and A4":"210"}},{"panel":"betweenness","set":{"A2 and I1":"196"}},{"panel":"communities","groups":[["A1","A2","A3","A4","A5","A6","A7","A8","A9","A10","A11","A12","A13","A14","A15","A16","B1","C1","C2","C3","C4","C5","C6","C7","C8","D1","E1","E3","E4","E5","F1","F3","F4","F5","H1","H3","H4","H5","I1","I2","I3","I4","I5","I6","I7","J1","J2","J3","J4","J5","J6"],["B2","B3","B4","B5","B6","B7","B8","B9","B10","B11","B12","B13","B14"],["D2","D3","D4","D5","D6","D7","D8","D9","D10","D11","D12"],["E2","E6","E7","E8","E9","E10"],["F2","F6","F7","F8","F9","F10"],["G1","G2","G3","G4","G5","G6","G7","G8"],["H2","H6","H7","H8","H9"]]}]},{"say":"Remove the edge between A1 and C1. Its betweenness, 168, ties for the highest with the edge between A2 and C1, and it comes first in gograph's AllEdges order. There are still 7 communities.","ops":[{"v":"A2","state":"idle"},{"v":"G1","state":"idle"},{"v":"A1","state":"current"},{"v":"C1","state":"current"},{"e":["A1","C1"],"state":"removed"},{"panel":"betweenness","unset":["A2 and G1","A2 and C1","A2 and A3","A2 and A4","A2 and I1"]},{"panel":"betweenness","set":{"A1 and C1":"168"}},{"panel":"betweenness","set":{"A2 and C1":"168"}},{"panel":"betweenness","set":{"A1 and A3":"154"}},{"panel":"betweenness","set":{"A1 and A4":"154"}},{"panel":"betweenness","set":{"A2 and A3":"154"}}]},{"say":"Remove the edge between A2 and C1. Its betweenness, 332, is the highest. There are still 7 communities.","ops":[{"v":"A1","state":"idle"},{"v":"A2","state":"current"},{"v":"C1","state":"current"},{"e":["A2","C1"],"state":"removed"},{"panel":"betweenness","unset":["A1 and C1","A2 and C1","A1 and A3","A1 and A4","A2 and A3"]},{"panel":"betweenness","set":{"A2 and C1":"332"}},{"panel":"betweenness","set":{"A2 and A3":"182"}},{"panel":"betweenness","set":{"A2 and A4":"182"}},{"panel":"betweenness","set":{"A2 and I1":"168"}},{"panel":"betweenness","set":{"A2 and J1":"159"}}]},{"say":"Remove the edge between C1 and D1. Its betweenness, 344, is the highest. That splits a community of 51 into parts of 43 and 8 vertices, so there are now 8 communities.","ops":[{"v":"A2","state":"idle"},{"v":"C1","state":"current"},{"v":"D1","state":"current"},{"e":["C1","D1"],"state":"removed"},{"panel":"betweenness","unset":["A2 and C1","A2 and A3","A2 and A4","A2 and I1","A2 and J1"]},{"panel":"betweenness","set":{"C1 and D1":"344"}},{"panel":"betweenness","set":{"A1 and D1":"189"}},{"panel":"betweenness","set":{"A2 and D1":"189"}},{"panel":"betweenness","set":{"A1 and A3":"154"}},{"panel":"betweenness","set":{"A1 and A4":"154"}},{"panel":"communities","groups":[["A1","A2","A3","A4","A5","A6","A7","A8","A9","A10","A11","A12","A13","A14","A15","A16","B1","D1","E1","E3","E4","E5","F1","F3","F4","F5","H1","H3","H4","H5","I1","I2","I3","I4","I5","I6","I7","J1","J2","J3","J4","J5","J6"],["B2","B3","B4","B5","B6","B7","B8","B9","B10","B11","B12","B13","B14"],["C1","C2","C3","C4","C5","C6","C7","C8"],["D2","D3","D4","D5","D6","D7","D8","D9","D10","D11","D12"],["E2","E6","E7","E8","E9","E10"],["F2","F6","F7","F8","F9","F10"],["G1","G2","G3","G4","G5","G6","G7","G8"],["H2","H6","H7","H8","H9"]]}]},{"say":"Done. Removing 12 edges left 8 communities.","ops":[{"v":"C1","state":"idle"},{"v":"D1","state":"idle"}]}],"traceNote":"","verification":"The steps come from a step-by-step copy of the algorithm. Its result is checked against gograph's on every start.","snippet":"communities, err := partition.GirvanNewman(g, 8)\nif err != nil {\n\treturn err\n}\nfor _, c := range communities {\n\tvar members []string\n\tfor _, v := range c.GetAllVertices() {\n\t\tmembers = append(members, v.Label())\n\t}\n\tfmt.Println(members)\n}"}
