Girvan-Newman

Splits an undirected graph into k communities by removing, one at a time, the edge that the most shortest paths cross.

Time complexity O(E·V·(V+E)), gograph function partition.GirvanNewman.

gograph keeps each undirected edge once per direction and gives each direction half of the edge's betweenness, so the scores shown are half the usual values.

Campus network

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.

An undirected graph with 100 vertices and 114 edges.

Split the campus network into 4 parts along the links that the most routes between devices cross.

Use it in Go

communities, err := partition.GirvanNewman(g, 4)
if err != nil {
	return err
}
for _, c := range communities {
	var members []string
	for _, v := range c.GetAllVertices() {
		members = append(members, v.Label())
	}
	fmt.Println(members)
}

Example graphs

• Friend groups, 12 vertices and 21 edges
• Office network, 13 vertices and 16 edges
• Karate club, 34 vertices and 78 edges
• Campus network, 100 vertices and 114 edges

More in Partitioning

• Maximal cliques: Finds every group of vertices that are all adjacent to each other and can't take one more vertex.
• Randomized k-cut: Splits an undirected graph into k groups by merging the ends of random edges until k groups are left, and cuts the edges between them.

All algorithms