partition

Documentation

Index

• func GirvanNewman[T comparable](g gograph.Graph[T], k int) ([]gograph.Graph[T], error)
• func MaximalCliques[T comparable](g gograph.Graph[T]) [][]*gograph.Vertex[T]
• type KCutResult
  • func RandomizedKCut[T comparable](g gograph.Graph[T], k int) (*KCutResult[T], error)

Functions

func GirvanNewman

func GirvanNewman[T comparable](g gograph.Graph[T], k int) ([]gograph.Graph[T], error)

GirvanNewman implements the Girvan-Newman community detection algorithm for undirected graphs. It partitions a graph into communities by iteratively removing edges with the highest betweenness centrality until either the specified number of connected components `k` is reached, or no edges remain if k <= 0.

The algorithm proceeds as follows:

1. Compute edge betweenness centrality for all edges using Brandes algorithm. - BFS is used from each vertex to determine the shortest paths. - Dependencies are accumulated to assign betweenness values to edges.
2. Identify edges with maximum betweenness.
3. Remove one or more edges with the highest betweenness.
4. Update connected components using a non-recursive BFS traversal.
5. Repeat steps 1-4 until the desired number of components (`k`) is reached. If k <= 0, continue until all edges are removed.

Important details:

• High betweenness edges typically act as bridges between clusters and are removed first, effectively separating communities.
• BFS is used exclusively for both shortest path computation and component identification to avoid recursion and stack overflow issues.
• The input graph `g` is cloned internally to prevent mutation.

Parameters:

• g: An instance of gograph.Graph[T] representing the undirected input graph.
• k: The desired number of communities (connected components). If k <= 0, the algorithm continues removing edges until no edges remain.

Returns:

• A slice of gograph.Graph[T], each representing a connected component (community).
• An error if the operation fails.

Time Complexity:

• Each iteration requires computing betweenness for all edges using BFS from each node.
• Let V = number of vertices, E = number of edges.
• Computing betweenness: O(V * (V + E)) per iteration.
• In the worst case, up to O(E) edges can be removed one by one.
• Total worst-case time complexity: O(E * V * (V + E)).

Space Complexity:

• Storing the cloned graph: O(V + E)
• BFS traversal queues and dependency maps: O(V + E)
• Storing betweenness values for edges: O(E)
• Total space complexity: O(V + E)

func MaximalCliques

func MaximalCliques[T comparable](g gograph.Graph[T]) [][]*gograph.Vertex[T]

MaximalCliques finds all maximal cliques in the input graph using the Bron–Kerbosch algorithm with pivot selection, degeneracy ordering, and bitsets.

A **clique** is a subset of vertices where every two distinct vertices are connected by an edge. A **maximal clique** is a clique that cannot be extended by adding another adjacent vertex.

This implementation is optimized for performance:

1. **Degeneracy ordering**: processes vertices in a specific order to reduce recursive calls and improve efficiency.
2. **Pivot selection**: selects a pivot vertex at each recursive call to reduce the number of branches.
3. **Bitsets**: represents candidate sets (P, X) efficiently using []uint64 to speed up set operations on large graphs.

Parameters:

• g: a gograph.Graph[T] representing the graph. T must be a comparable type. Each vertex in the graph can be accessed via g.GetAllVertices() and neighbors via Vertex.Neighbors().

Returns:

• [][]*gograph.Vertex[T]: a slice of maximal cliques. Each clique is a slice of pointers to Vertex[T]. Vertices in a clique are guaranteed to be fully connected, and no clique is a subset of another.

Complexity:

• **Time Complexity**: O(3^(n/3)) in the worst case for general graphs, where n is the number of vertices. This is the known bound for enumerating all maximal cliques. In practice, degeneracy ordering + pivoting reduces the number of recursive calls significantly on sparse graphs.
• **Space Complexity**: O(n^2 / 64) for bitsets plus O(k*n) for storing cliques, where k is the number of maximal cliques. Additional recursion stack space is O(n) in depth.

Example usage:

g := gograph.New[string]()
a := g.AddVertexByLabel("A")
b := g.AddVertexByLabel("B")
c := g.AddVertexByLabel("C")
_, _ = g.AddEdge(a, b)
_, _ = g.AddEdge(b, c)
_, _ = g.AddEdge(c, a)

cliques := MaximalCliques(g)
for _, clique := range cliques {
    for _, v := range clique {
        fmt.Print(v.Label(), " ")
    }
    fmt.Println()
}

Notes:

• The function returns the actual Vertex pointers from the input graph; do not modify the vertices while iterating the results.
• The order of cliques or vertices within a clique is not guaranteed. If deterministic ordering is required, use a normalization function (e.g., sort by vertex label).

Types

type KCutResult

type KCutResult[T comparable] struct {
	Supernodes [][]*gograph.Vertex[T]
	CutEdges   []*gograph.Edge[T]
}

func RandomizedKCut

func RandomizedKCut[T comparable](g gograph.Graph[T], k int) (*KCutResult[T], error)

RandomizedKCut computes an approximate k-cut of an undirected graph using a randomized contraction algorithm (generalization of Karger’s min-cut).

The algorithm works as follows:

1. Initialize each vertex as its own supernode.
2. While the number of supernodes > k: a. Pick a random edge (u, v) from the remaining edges. b. Contract the edge: merge vertices u and v into a single supernode. - Redirect all edges of v to u. - Remove self-loops.
3. When exactly k supernodes remain, the remaining edges between supernodes form the approximate k-cut.
4. Return both the supernodes and the edges crossing between them.

Notes:

• This is a randomized algorithm; different runs may produce different cuts.
• Probability of finding the true minimum k-cut decreases with graph size and k. Repeating the algorithm multiple times improves the chances.
• Only applicable to undirected graphs; for directed graphs, results are approximate and may not correspond to a global min-cut.
• The returned supernodes are slices of vertex pointers representing the contracted vertex groups after k-way partitioning.
• The returned cut edges are edges that connect different supernodes in the original graph.

Time Complexity: O(n * m) per run, where n is the number of vertices and m is the number of edges in the graph.

Space Complexity: O(n + m) for storing vertex sets and edge lists.

Parameters:

g - The input graph implementing Graph[T] interface.
k - The number of supernodes desired in the partition (k ≥ 2).

Returns:

*KCutResult[T] - Struct containing:
    - Supernodes: slice of supernodes (vertex groups) after contraction.
    - CutEdges: edges connecting different supernodes (the k-cut).
error - Non-nil if k < 2 or graph has fewer than k vertices.

Example usage:

g := NewBaseGraph[string](false, false) // undirected, unweighted
a := g.AddVertexByLabel("A")
b := g.AddVertexByLabel("B")
g.AddEdge(a, b)
result, err := RandomizedKCut(g, 2)
if err != nil { log.Fatal(err) }
fmt.Println("Supernodes:", result.Supernodes)
fmt.Println("Cut edges:", result.CutEdges)