{"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":"karate-club","name":"Karate club","description":"The 34 members of a university karate club, numbered 1 to 34 as in the study. Each edge joins two members who also spent time together outside the club's classes and meetings. A dispute between the instructor (1) and an officer (34) split the club in two, and most members sit near the side they joined.","family":"undirected","directed":false,"weighted":false,"acyclic":false,"vertices":[{"id":"1","x":590,"y":680},{"id":"2","x":640,"y":560},{"id":"3","x":420,"y":520},{"id":"4","x":470,"y":760},{"id":"5","x":680,"y":850},{"id":"6","x":750,"y":860},{"id":"7","x":820,"y":760},{"id":"8","x":390,"y":660},{"id":"9","x":520,"y":430},{"id":"10","x":590,"y":230},{"id":"11","x":590,"y":930},{"id":"12","x":400,"y":900},{"id":"13","x":490,"y":890},{"id":"14","x":590,"y":480},{"id":"15","x":460,"y":80},{"id":"16","x":380,"y":70},{"id":"17","x":950,"y":940},{"id":"18","x":830,"y":560},{"id":"19","x":540,"y":110},{"id":"20","x":770,"y":450},{"id":"21","x":90,"y":220},{"id":"22","x":820,"y":640},{"id":"23","x":290,"y":70},{"id":"24","x":120,"y":300},{"id":"25","x":120,"y":690},{"id":"26","x":50,"y":570},{"id":"27","x":220,"y":60},{"id":"28","x":210,"y":490},{"id":"29","x":390,"y":440},{"id":"30","x":170,"y":190},{"id":"31","x":640,"y":300},{"id":"32","x":280,"y":570},{"id":"33","x":250,"y":340},{"id":"34","x":440,"y":260}],"edges":[{"from":"1","to":"2"},{"from":"1","to":"3"},{"from":"1","to":"4"},{"from":"1","to":"5"},{"from":"1","to":"6"},{"from":"1","to":"7"},{"from":"1","to":"8"},{"from":"1","to":"9"},{"from":"1","to":"11"},{"from":"1","to":"12"},{"from":"1","to":"13"},{"from":"1","to":"14"},{"from":"1","to":"18"},{"from":"1","to":"20"},{"from":"1","to":"22"},{"from":"1","to":"32"},{"from":"2","to":"3"},{"from":"2","to":"4"},{"from":"2","to":"8"},{"from":"2","to":"14"},{"from":"2","to":"18"},{"from":"2","to":"20"},{"from":"2","to":"22"},{"from":"2","to":"31"},{"from":"3","to":"4"},{"from":"3","to":"8"},{"from":"3","to":"9"},{"from":"3","to":"10"},{"from":"3","to":"14"},{"from":"3","to":"28"},{"from":"3","to":"29"},{"from":"3","to":"33"},{"from":"4","to":"8"},{"from":"4","to":"13"},{"from":"4","to":"14"},{"from":"5","to":"7"},{"from":"5","to":"11"},{"from":"6","to":"7"},{"from":"6","to":"11"},{"from":"6","to":"17"},{"from":"7","to":"17"},{"from":"9","to":"31"},{"from":"9","to":"33"},{"from":"9","to":"34"},{"from":"10","to":"34"},{"from":"14","to":"34"},{"from":"15","to":"33"},{"from":"15","to":"34"},{"from":"16","to":"33"},{"from":"16","to":"34"},{"from":"19","to":"33"},{"from":"19","to":"34"},{"from":"20","to":"34"},{"from":"21","to":"33"},{"from":"21","to":"34"},{"from":"23","to":"33"},{"from":"23","to":"34"},{"from":"24","to":"26"},{"from":"24","to":"28"},{"from":"24","to":"30"},{"from":"24","to":"33"},{"from":"24","to":"34"},{"from":"25","to":"26"},{"from":"25","to":"28"},{"from":"25","to":"32"},{"from":"26","to":"32"},{"from":"27","to":"30"},{"from":"27","to":"34"},{"from":"28","to":"34"},{"from":"29","to":"32"},{"from":"29","to":"34"},{"from":"30","to":"33"},{"from":"30","to":"34"},{"from":"31","to":"33"},{"from":"31","to":"34"},{"from":"32","to":"33"},{"from":"32","to":"34"},{"from":"33","to":"34"}],"source":"W. W. Zachary, \"An information flow model for conflict and fission in small groups\", Journal of Anthropological Research 33 (1977).","details":{"vertices":34,"edges":78,"directed":false,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.13903743315508021,"degree":{"min":1,"avg":4.588235294117647,"max":17},"selfLoops":0,"components":1}},"problem":"The club split in two after the dispute. Using only who spent time with whom, predict which side each member joined.","params":{"k":2},"result":{"kind":"sets","sets":[["1","2","4","5","6","7","8","11","12","13","14","17","18","20","22"],["3","9","10","15","16","19","21","23","24","25","26","27","28","29","30","31","32","33","34"]]},"answer":"The 2 communities have 15 and 19 vertices: 1, 2, 4, 5, 6, 7, 8, 11, 12, 13 and 5 more; 3, 9, 10, 15, 16, 19, 21, 23, 24, 25 and 9 more.","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 = 2 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":[["1","2","3","4","5","6","7","8","9","10","11","12","13","14","15","16","17","18","19","20","21","22","23","24","25","26","27","28","29","30","31","32","33","34"]]}]},{"say":"Remove the edge between 1 and 32. Its betweenness, 71.39, is the highest. The graph is still in one piece.","ops":[{"v":"1","state":"current"},{"v":"32","state":"current"},{"e":["1","32"],"state":"removed"},{"panel":"betweenness","set":{"1 and 32":"71.39"}},{"panel":"betweenness","set":{"1 and 7":"43.83"}},{"panel":"betweenness","set":{"1 and 6":"43.83"}},{"panel":"betweenness","set":{"1 and 3":"43.64"}},{"panel":"betweenness","set":{"1 and 9":"41.65"}}]},{"say":"Remove the edge between 1 and 3. Its betweenness, 66.9, is the highest. The graph is still in one piece.","ops":[{"v":"32","state":"idle"},{"v":"1","state":"current"},{"v":"3","state":"current"},{"e":["1","3"],"state":"removed"},{"panel":"betweenness","unset":["1 and 32","1 and 7","1 and 6","1 and 3","1 and 9"]},{"panel":"betweenness","set":{"1 and 3":"66.9"}},{"panel":"betweenness","set":{"1 and 9":"55.67"}},{"panel":"betweenness","set":{"3 and 33":"49.32"}},{"panel":"betweenness","set":{"14 and 34":"48.59"}},{"panel":"betweenness","set":{"1 and 6":"43.83"}}]},{"say":"Remove the edge between 1 and 9. Its betweenness, 77.32, is the highest. The graph is still in one piece.","ops":[{"v":"3","state":"idle"},{"v":"1","state":"current"},{"v":"9","state":"current"},{"e":["1","9"],"state":"removed"},{"panel":"betweenness","unset":["1 and 3","1 and 9","3 and 33","14 and 34","1 and 6"]},{"panel":"betweenness","set":{"1 and 9":"77.32"}},{"panel":"betweenness","set":{"14 and 34":"57.27"}},{"panel":"betweenness","set":{"20 and 34":"51.29"}},{"panel":"betweenness","set":{"1 and 6":"43.83"}},{"panel":"betweenness","set":{"1 and 7":"43.83"}}]},{"say":"Remove the edge between 14 and 34. Its betweenness, 82, is the highest. The graph is still in one piece.","ops":[{"v":"1","state":"idle"},{"v":"9","state":"idle"},{"v":"14","state":"current"},{"v":"34","state":"current"},{"e":["14","34"],"state":"removed"},{"panel":"betweenness","unset":["1 and 9","14 and 34","20 and 34","1 and 6","1 and 7"]},{"panel":"betweenness","set":{"14 and 34":"82"}},{"panel":"betweenness","set":{"20 and 34":"75.51"}},{"panel":"betweenness","set":{"1 and 14":"69.12"}},{"panel":"betweenness","set":{"1 and 20":"62.24"}},{"panel":"betweenness","set":{"1 and 7":"43.83"}}]},{"say":"Remove the edge between 20 and 34. Its betweenness, 123.23, is the highest. The graph is still in one piece.","ops":[{"v":"14","state":"idle"},{"v":"20","state":"current"},{"v":"34","state":"current"},{"e":["20","34"],"state":"removed"},{"panel":"betweenness","unset":["14 and 34","20 and 34","1 and 14","1 and 20","1 and 7"]},{"panel":"betweenness","set":{"20 and 34":"123.23"}},{"panel":"betweenness","set":{"1 and 20":"107.74"}},{"panel":"betweenness","set":{"3 and 33":"53.25"}},{"panel":"betweenness","set":{"1 and 6":"43.83"}},{"panel":"betweenness","set":{"1 and 7":"43.83"}}]},{"say":"Remove the edge between 3 and 33. Its betweenness, 100.21, is the highest. The graph is still in one piece.","ops":[{"v":"20","state":"idle"},{"v":"34","state":"idle"},{"v":"3","state":"current"},{"v":"33","state":"current"},{"e":["3","33"],"state":"removed"},{"panel":"betweenness","unset":["20 and 34","1 and 20","3 and 33","1 and 6","1 and 7"]},{"panel":"betweenness","set":{"3 and 33":"100.21"}},{"panel":"betweenness","set":{"2 and 31":"85.34"}},{"panel":"betweenness","set":{"1 and 2":"72.84"}},{"panel":"betweenness","set":{"2 and 3":"61.36"}},{"panel":"betweenness","set":{"3 and 4":"57.96"}}]},{"say":"Remove the edge between 2 and 31. Its betweenness, 143.63, is the highest. The graph is still in one piece.","ops":[{"v":"3","state":"idle"},{"v":"33","state":"idle"},{"v":"2","state":"current"},{"v":"31","state":"current"},{"e":["2","31"],"state":"removed"},{"panel":"betweenness","unset":["3 and 33","2 and 31","1 and 2","2 and 3","3 and 4"]},{"panel":"betweenness","set":{"2 and 31":"143.63"}},{"panel":"betweenness","set":{"1 and 2":"101.59"}},{"panel":"betweenness","set":{"31 and 34":"77.88"}},{"panel":"betweenness","set":{"31 and 33":"62.85"}},{"panel":"betweenness","set":{"3 and 28":"60.07"}}]},{"say":"Remove the edge between 2 and 3. Its betweenness, 109.25, is the highest. The graph is still in one piece.","ops":[{"v":"31","state":"idle"},{"v":"2","state":"current"},{"v":"3","state":"current"},{"e":["2","3"],"state":"removed"},{"panel":"betweenness","unset":["2 and 31","1 and 2","31 and 34","31 and 33","3 and 28"]},{"panel":"betweenness","set":{"2 and 3":"109.25"}},{"panel":"betweenness","set":{"3 and 9":"95.08"}},{"panel":"betweenness","set":{"3 and 28":"90.08"}},{"panel":"betweenness","set":{"3 and 4":"71.25"}},{"panel":"betweenness","set":{"3 and 29":"65.5"}}]},{"say":"Remove the edge between 3 and 4. Its betweenness, 107.67, is the highest. The graph is still in one piece.","ops":[{"v":"2","state":"idle"},{"v":"3","state":"current"},{"v":"4","state":"current"},{"e":["3","4"],"state":"removed"},{"panel":"betweenness","unset":["2 and 3","3 and 9","3 and 28","3 and 4","3 and 29"]},{"panel":"betweenness","set":{"3 and 4":"107.67"}},{"panel":"betweenness","set":{"3 and 9":"95.08"}},{"panel":"betweenness","set":{"3 and 28":"90.08"}},{"panel":"betweenness","set":{"3 and 8":"88.92"}},{"panel":"betweenness","set":{"3 and 14":"88.92"}}]},{"say":"Remove the edge between 3 and 8. Its betweenness, 142.75, ties for the highest with the edge between 3 and 14, and it comes first in gograph's AllEdges order. The graph is still in one piece.","ops":[{"v":"4","state":"idle"},{"v":"3","state":"current"},{"v":"8","state":"current"},{"e":["3","8"],"state":"removed"},{"panel":"betweenness","unset":["3 and 4","3 and 9","3 and 28","3 and 8","3 and 14"]},{"panel":"betweenness","set":{"3 and 8":"142.75"}},{"panel":"betweenness","set":{"3 and 14":"142.75"}},{"panel":"betweenness","set":{"3 and 9":"95.08"}},{"panel":"betweenness","set":{"1 and 8":"94.75"}},{"panel":"betweenness","set":{"1 and 14":"94.75"}}]},{"say":"Remove the edge between 3 and 14. Its betweenness, 285, is the highest. That splits the graph into parts of 19 and 15 vertices, so there are now 2 communities.","ops":[{"v":"8","state":"idle"},{"v":"3","state":"current"},{"v":"14","state":"current"},{"e":["3","14"],"state":"removed"},{"panel":"betweenness","unset":["3 and 8","3 and 14","3 and 9","1 and 8","1 and 14"]},{"panel":"betweenness","set":{"3 and 14":"285"}},{"panel":"betweenness","set":{"1 and 14":"186.67"}},{"panel":"betweenness","set":{"3 and 9":"95.08"}},{"panel":"betweenness","set":{"3 and 28":"90.08"}},{"panel":"betweenness","set":{"3 and 29":"65.5"}},{"panel":"communities","groups":[["1","2","4","5","6","7","8","11","12","13","14","17","18","20","22"],["3","9","10","15","16","19","21","23","24","25","26","27","28","29","30","31","32","33","34"]]}]},{"say":"Done. Removing 11 edges left 2 communities. gograph returns each community with every edge between its members, so the removed edge between 3 and 33 comes back.","ops":[{"v":"3","state":"idle"},{"v":"14","state":"idle"},{"e":["3","33"],"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, 2)\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}"}
