{"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":"office-network","name":"Office network","description":"Switches and rooms in a four-team office, wired through a core switch.","family":"undirected","directed":false,"weighted":false,"acyclic":false,"vertices":[{"id":"Core","x":512,"y":320},{"id":"Sales","x":320,"y":192},{"id":"Support","x":704,"y":192},{"id":"Ops","x":704,"y":448},{"id":"Dev","x":320,"y":448},{"id":"Uplink","x":512,"y":64},{"id":"Sales 1","x":128,"y":128},{"id":"Lab","x":160,"y":320},{"id":"Dev 1","x":128,"y":528},{"id":"Dev 2","x":512,"y":576},{"id":"Support 1","x":896,"y":112},{"id":"Shared","x":912,"y":304},{"id":"Ops 1","x":896,"y":544}],"edges":[{"from":"Core","to":"Sales"},{"from":"Core","to":"Support"},{"from":"Core","to":"Ops"},{"from":"Core","to":"Dev"},{"from":"Sales","to":"Uplink"},{"from":"Sales","to":"Sales 1"},{"from":"Sales","to":"Lab"},{"from":"Support","to":"Uplink"},{"from":"Support","to":"Support 1"},{"from":"Support","to":"Shared"},{"from":"Ops","to":"Shared"},{"from":"Ops","to":"Ops 1"},{"from":"Dev","to":"Lab"},{"from":"Dev","to":"Dev 1"},{"from":"Dev","to":"Dev 2"},{"from":"Lab","to":"Dev 1"}],"details":{"vertices":13,"edges":16,"directed":false,"weighted":false,"acyclic":false,"negativeWeights":false,"density":0.20512820512820512,"degree":{"min":1,"avg":2.4615384615384617,"max":4},"selfLoops":0,"components":1}},"problem":"Split the office network into 3 parts along the links that the most routes between rooms cross.","params":{"k":3},"result":{"kind":"sets","sets":[["Core","Ops","Ops 1","Shared","Support","Support 1"],["Dev","Dev 1","Dev 2","Lab"],["Sales","Sales 1","Uplink"]]},"answer":"The 3 communities have 6, 4 and 3 vertices: Core, Ops, Ops 1, Shared, Support and Support 1; Dev, Dev 1, Dev 2 and Lab; Sales, Sales 1 and Uplink.","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 = 3 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":[["Core","Sales","Support","Ops","Dev","Uplink","Sales 1","Lab","Dev 1","Dev 2","Support 1","Shared","Ops 1"]]}]},{"say":"Remove the edge between Core and Dev. Its betweenness, 23.9, is the highest. The graph is still in one piece.","ops":[{"v":"Core","state":"current"},{"v":"Dev","state":"current"},{"e":["Core","Dev"],"state":"removed"},{"panel":"betweenness","set":{"Core and Dev":"23.9"}},{"panel":"betweenness","set":{"Core and Ops":"20.4"}},{"panel":"betweenness","set":{"Core and Support":"18.23"}},{"panel":"betweenness","set":{"Core and Sales":"15.73"}},{"panel":"betweenness","set":{"Sales and Lab":"12.1"}}]},{"say":"Remove the edge between Sales and Lab. Its betweenness, 36, is the highest. Dev, Lab, Dev 1 and Dev 2 split off, so there are now 2 communities.","ops":[{"v":"Core","state":"idle"},{"v":"Dev","state":"idle"},{"v":"Sales","state":"current"},{"v":"Lab","state":"current"},{"e":["Sales","Lab"],"state":"removed"},{"panel":"betweenness","unset":["Core and Dev","Core and Ops","Core and Support","Core and Sales","Sales and Lab"]},{"panel":"betweenness","set":{"Sales and Lab":"36"}},{"panel":"betweenness","set":{"Core and Sales":"29.17"}},{"panel":"betweenness","set":{"Dev and Lab":"20"}},{"panel":"betweenness","set":{"Core and Ops":"19.83"}},{"panel":"betweenness","set":{"Sales and Uplink":"15.17"}},{"panel":"communities","groups":[["Core","Sales","Support","Ops","Uplink","Sales 1","Support 1","Shared","Ops 1"],["Dev","Lab","Dev 1","Dev 2"]]}]},{"say":"Remove the edge between Core and Sales. Its betweenness, 10.5, ties for the highest with the edge between Core and Ops, and it comes first in gograph's AllEdges order. There are still 2 communities.","ops":[{"v":"Lab","state":"idle"},{"v":"Core","state":"current"},{"v":"Sales","state":"current"},{"e":["Core","Sales"],"state":"removed"},{"panel":"betweenness","unset":["Sales and Lab","Core and Sales","Dev and Lab","Core and Ops","Sales and Uplink"]},{"panel":"betweenness","set":{"Core and Sales":"10.5"}},{"panel":"betweenness","set":{"Core and Ops":"10.5"}},{"panel":"betweenness","set":{"Core and Support":"8.33"}},{"panel":"betweenness","set":{"Sales and Sales 1":"8"}},{"panel":"betweenness","set":{"Support and Support 1":"8"}}]},{"say":"Remove the edge between Support and Uplink. Its betweenness, 18, is the highest. Sales, Uplink and Sales 1 split off, so there are now 3 communities.","ops":[{"v":"Core","state":"idle"},{"v":"Sales","state":"idle"},{"v":"Support","state":"current"},{"v":"Uplink","state":"current"},{"e":["Support","Uplink"],"state":"removed"},{"panel":"betweenness","unset":["Core and Sales","Core and Ops","Core and Support","Sales and Sales 1","Support and Support 1"]},{"panel":"betweenness","set":{"Support and Uplink":"18"}},{"panel":"betweenness","set":{"Sales and Uplink":"14"}},{"panel":"betweenness","set":{"Core and Support":"10.5"}},{"panel":"betweenness","set":{"Support and Shared":"10.5"}},{"panel":"betweenness","set":{"Sales and Sales 1":"8"}},{"panel":"communities","groups":[["Core","Support","Ops","Support 1","Shared","Ops 1"],["Sales","Uplink","Sales 1"],["Dev","Lab","Dev 1","Dev 2"]]}]},{"say":"Done. Removing 4 edges left 3 communities.","ops":[{"v":"Support","state":"idle"},{"v":"Uplink","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, 3)\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}"}
