Documentation
¶
Overview ¶
Package community provides pluggable graph community detection algorithms.
Each algorithm implements the Algorithm interface. The registry maps string names to implementations so callers can select by name (CLI flag, MCP param, export option).
To add a new algorithm:
- Create a file (e.g. leiden.go) implementing Algorithm
- Register it in init() or Registry
Index ¶
- Constants
- Variables
- func LoadAssignments(ctx context.Context, store types.GraphStore) (map[types.Hash]int, error)
- func Names() []string
- func SaveAssignments(ctx context.Context, store types.GraphStore, assignments map[types.Hash]int) error
- func SaveChangedAssignments(ctx context.Context, store types.GraphStore, ...) error
- type Algorithm
- type Graph
- type IncrementalAlgorithm
- type LabelPropagation
- type Louvain
- type WeightedEdge
Constants ¶
const Default = "louvain"
Default is the algorithm used when none is specified.
const NoteKey = "community_id"
NoteKey is the notes table key used for community assignments.
Variables ¶
var Registry = map[string]Algorithm{ "louvain": &Louvain{Resolution: 1.0, MaxPasses: 20}, "louvain-fine": &Louvain{Resolution: 0.3, MaxPasses: 20}, "label-propagation": &LabelPropagation{MaxIterations: 50}, }
Registry maps algorithm names to implementations.
Functions ¶
func LoadAssignments ¶ added in v0.4.0
LoadAssignments retrieves previously persisted community assignments from the notes table. Returns nil (not an error) if no assignments are stored.
func SaveAssignments ¶ added in v0.4.0
func SaveAssignments(ctx context.Context, store types.GraphStore, assignments map[types.Hash]int) error
SaveAssignments persists community assignments to the notes table. Each node's community ID is stored as a note with key "community_id". Uses BatchPutNotes when available for ~100x speedup on large graphs.
func SaveChangedAssignments ¶ added in v0.4.0
func SaveChangedAssignments(ctx context.Context, store types.GraphStore, current, previous map[types.Hash]int) error
SaveChangedAssignments persists only the assignments that differ from previous. Nodes whose community ID is unchanged are skipped. Nodes in previous but not in current are deleted (node was removed from graph). This makes save cost proportional to the number of changes, not the total graph size.
Types ¶
type Algorithm ¶
Algorithm detects communities in a graph. Returns a map from node hash to community ID (int). Community IDs should be contiguous starting from 0.
type Graph ¶
type Graph struct {
Nodes []types.Hash
Adj map[types.Hash][]WeightedEdge
NodeSet map[types.Hash]bool
EdgeCount int
}
Graph holds the adjacency list and node set for community detection.
type IncrementalAlgorithm ¶ added in v0.4.0
type IncrementalAlgorithm interface {
Algorithm
DetectIncremental(g *Graph, previous map[types.Hash]int, changedNodes map[types.Hash]bool) map[types.Hash]int
}
IncrementalAlgorithm extends Algorithm with incremental detection. DetectIncremental seeds community assignments from previous results and only allows changedNodes to move. Nodes not in changedNodes keep their previous assignment (frozen). This enables O(changed) detection instead of O(all) after a partial re-index.
If previous is nil or empty, falls back to full Detect behavior. changedNodes is the set of nodes whose edges may have changed.
type LabelPropagation ¶
type LabelPropagation struct {
MaxIterations int
}
LabelPropagation implements the label propagation community detection algorithm. Each node adopts the most common label among its neighbors. Fast and simple but non-deterministic (results vary between runs).
func (*LabelPropagation) DetectIncremental ¶ added in v0.4.0
func (lp *LabelPropagation) DetectIncremental(g *Graph, previous map[types.Hash]int, changedNodes map[types.Hash]bool) map[types.Hash]int
DetectIncremental runs label propagation seeded from previous assignments. Only changedNodes are iterated; frozen nodes keep their previous label. Falls back to full Detect if previous is nil/empty.
func (*LabelPropagation) Name ¶
func (lp *LabelPropagation) Name() string
type Louvain ¶
Louvain implements single-pass Louvain modularity optimization. Resolution controls granularity: lower values produce fewer, larger communities.
func (*Louvain) DetectIncremental ¶ added in v0.4.0
func (l *Louvain) DetectIncremental(g *Graph, previous map[types.Hash]int, changedNodes map[types.Hash]bool) map[types.Hash]int
DetectIncremental runs Louvain seeded from previous community assignments. Only nodes in changedNodes are allowed to move; all other nodes keep their previous assignment. Falls back to full Detect if previous is nil/empty.
type WeightedEdge ¶
WeightedEdge represents a graph edge with a weight (typically confidence).
Source Files