Documentation
¶
Overview ¶
Package community implements community detection algorithms for undirected graphs.
v1 includes:
- Leiden — Traag-Waltman-van Eck 2019, modularity-optimising community detection with the modularity-and-connectivity guarantees the canonical Louvain algorithm lacks.
- LabelPropagation — Raghavan-Albert-Kumara 2007, the near-linear-time simple counterpart.
Index ¶
- type LabelPropagationOptions
- type LeidenOptions
- type Partition
- func LabelPropagation[W any](c *csr.CSR[W], opts LabelPropagationOptions) Partition
- func LabelPropagationCtx[W any](ctx context.Context, c *csr.CSR[W], opts LabelPropagationOptions) (Partition, error)
- func Leiden[W any](c *csr.CSR[W], opts LeidenOptions) Partition
- func LeidenCtx[W any](ctx context.Context, c *csr.CSR[W], opts LeidenOptions) (Partition, error)
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type LabelPropagationOptions ¶
type LabelPropagationOptions struct {
MaxIterations int
}
LabelPropagationOptions configures LabelPropagation.
func DefaultLabelPropagationOptions ¶
func DefaultLabelPropagationOptions() LabelPropagationOptions
DefaultLabelPropagationOptions returns reasonable defaults.
type LeidenOptions ¶
type LeidenOptions struct {
// MaxIterations bounds the number of local-moving sweeps per pass.
MaxIterations int
// MaxPasses bounds the number of Leiden passes (local-move +
// refine + aggregate) before the algorithm stops.
MaxPasses int
// Resolution scales the modularity expectation term (typically 1.0).
// Larger values bias toward smaller communities; smaller values
// toward fewer larger communities.
Resolution float64
}
LeidenOptions configures Leiden.
func DefaultLeidenOptions ¶
func DefaultLeidenOptions() LeidenOptions
DefaultLeidenOptions returns the default parameters.
type Partition ¶
Partition is the result of a community-detection run.
Community is a NodeID-indexed slice of length MaxNodeID(): for each live NodeID it holds a community ID in [0, NumCommunities); for ghost NodeID slots (created by sharded packing on small graphs) it holds the sentinel value -1. NumCommunities counts only live communities.
func LabelPropagation ¶
func LabelPropagation[W any](c *csr.CSR[W], opts LabelPropagationOptions) Partition
LabelPropagation runs the Raghavan-Albert-Kumara 2007 algorithm: every live node iteratively adopts the most common label among its neighbours, breaking ties deterministically by the smaller label ID. Converges when no node changes label or after MaxIterations.
Only live NodeIDs participate; ghost slots receive the sentinel -1 in the returned partition.
Complexity is O(k * (V + E)) for k iterations.
Example ¶
ExampleLabelPropagation detects communities with the near-linear label-propagation algorithm. As with Leiden, the raw labels are not asserted; the example checks the community count and that each dense triangle is recovered as a single group.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph/adjlist"
"github.com/FlavioCFOliveira/GoGraph/graph/csr"
"github.com/FlavioCFOliveira/GoGraph/search/community"
)
// buildTwoTriangles returns an undirected CSR of two triangles
// {0,1,2} and {3,4,5} linked by a single bridge edge 2-3, together
// with its mapper. It is the canonical fixture for showing a
// community detector separating two densely-knit groups.
func buildTwoTriangles() (*csr.CSR[struct{}], *adjlist.AdjList[int, struct{}]) {
a := adjlist.New[int, struct{}](adjlist.Config{Directed: false})
for _, e := range [][2]int{{0, 1}, {1, 2}, {0, 2}, {3, 4}, {4, 5}, {3, 5}} {
_ = a.AddEdge(e[0], e[1], struct{}{})
}
_ = a.AddEdge(2, 3, struct{}{})
return csr.BuildFromAdjList(a), a
}
// sameCommunity reports whether every listed user value shares one
// community label in the partition, resolving each through the mapper.
func sameCommunity(p community.Partition, m *adjlist.AdjList[int, struct{}], values ...int) bool {
first, _ := m.Mapper().Lookup(values[0])
want := p.Community[first]
for _, v := range values[1:] {
id, _ := m.Mapper().Lookup(v)
if p.Community[id] != want {
return false
}
}
return true
}
func main() {
c, m := buildTwoTriangles()
p := community.LabelPropagation(c, community.DefaultLabelPropagationOptions())
fmt.Printf("communities: %d\n", p.NumCommunities)
fmt.Printf("triangle {0,1,2} together: %v\n", sameCommunity(p, m, 0, 1, 2))
fmt.Printf("triangle {3,4,5} together: %v\n", sameCommunity(p, m, 3, 4, 5))
}
Output: communities: 2 triangle {0,1,2} together: true triangle {3,4,5} together: true
func LabelPropagationCtx ¶
func LabelPropagationCtx[W any](ctx context.Context, c *csr.CSR[W], opts LabelPropagationOptions) (Partition, error)
LabelPropagationCtx is the context-aware variant of LabelPropagation. ctx.Err() is checked at every iteration boundary; on cancellation returns (zero Partition, wrapped ctx.Err()).
func Leiden ¶
func Leiden[W any](c *csr.CSR[W], opts LeidenOptions) Partition
Leiden runs the Traag-Waltman-van Eck Leiden community-detection algorithm on the undirected graph c.
Three phases per pass:
- Local moving — each node greedily moves to the community that maximises the modularity gain ΔQ (Newman's formula).
- Refinement — within each community, restart with singletons and allow moves only inside the parent community, producing a well-separated refined partition. This is the Leiden-vs-Louvain guarantee that no community is internally poorly connected.
- Aggregation — contract each refined sub-community into a single super-node; iterate on the smaller graph.
Repeats passes until modularity no longer improves or MaxPasses is reached. A final splitDisconnected post-pass guarantees every returned community is internally connected.
Only live NodeIDs (those with at least one incident edge) are assigned to a community; ghost slots receive the sentinel -1.
Concurrency: safe to invoke from any number of goroutines on a shared CSR.
Determinism ¶
Leiden's local-move and refinement phases visit nodes in NodeID order — the inner loops iterate over [0, MaxNodeID) without randomisation. The tie-breaking rule for ΔQ comparisons is "first candidate community wins": when two destination communities yield equal modularity gain, the algorithm keeps the community with the lower NodeID anchor. This makes Leiden bit-for-bit reproducible across runs on the same input, on the same machine, with the same Go toolchain, provided opts is unchanged.
Two callers running Leiden on the same csr.CSR snapshot in parallel are guaranteed to produce the same Partition (modulo goroutine scheduling on the sequential algorithm — there is no internal goroutine pool). Across different machines the result is still deterministic as long as the floating-point implementation is IEEE-754 compliant; the small floating-point rounding deltas between architectures do not cross the equal-modularity tie-breaking threshold for typical inputs but pathological cases at exact equality may diverge.
Example ¶
ExampleLeiden detects communities with the Leiden algorithm. The concrete community IDs are an implementation detail, so the example asserts stable derived facts: the number of communities found and that each triangle stays together while the two triangles separate.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph/adjlist"
"github.com/FlavioCFOliveira/GoGraph/graph/csr"
"github.com/FlavioCFOliveira/GoGraph/search/community"
)
// buildTwoTriangles returns an undirected CSR of two triangles
// {0,1,2} and {3,4,5} linked by a single bridge edge 2-3, together
// with its mapper. It is the canonical fixture for showing a
// community detector separating two densely-knit groups.
func buildTwoTriangles() (*csr.CSR[struct{}], *adjlist.AdjList[int, struct{}]) {
a := adjlist.New[int, struct{}](adjlist.Config{Directed: false})
for _, e := range [][2]int{{0, 1}, {1, 2}, {0, 2}, {3, 4}, {4, 5}, {3, 5}} {
_ = a.AddEdge(e[0], e[1], struct{}{})
}
_ = a.AddEdge(2, 3, struct{}{})
return csr.BuildFromAdjList(a), a
}
// sameCommunity reports whether every listed user value shares one
// community label in the partition, resolving each through the mapper.
func sameCommunity(p community.Partition, m *adjlist.AdjList[int, struct{}], values ...int) bool {
first, _ := m.Mapper().Lookup(values[0])
want := p.Community[first]
for _, v := range values[1:] {
id, _ := m.Mapper().Lookup(v)
if p.Community[id] != want {
return false
}
}
return true
}
func main() {
c, m := buildTwoTriangles()
p := community.Leiden(c, community.DefaultLeidenOptions())
fmt.Printf("communities: %d\n", p.NumCommunities)
fmt.Printf("triangle {0,1,2} together: %v\n", sameCommunity(p, m, 0, 1, 2))
fmt.Printf("triangle {3,4,5} together: %v\n", sameCommunity(p, m, 3, 4, 5))
fmt.Printf("the two triangles merged: %v\n", sameCommunity(p, m, 0, 3))
}
Output: communities: 2 triangle {0,1,2} together: true triangle {3,4,5} together: true the two triangles merged: false
Source Files