Documentation
¶
Overview ¶
Package cluster — Leiden community detection (V0 implementation).
Goal: well-connected communities maximizing modularity at a given resolution γ. We follow the structure of the reference Java implementation at github.com/CWTSLeiden/networkanalysis, simplified to undirected unweighted graphs (V0 only treats edge multiplicity).
Three nested phases per outer iteration:
- Local moving — for each node, move it to the neighboring community that maximizes ΔQ (modularity gain).
- Refinement — within each community, restart with singletons and re-aggregate to guarantee well-connectedness.
- Aggregation — collapse each refined community into a single super-node and recurse.
Stops when no node move yields ΔQ > 0 across an entire pass.
Package cluster builds two hierarchies for the CKG graph: pkg_tree (deterministic, derived from package paths) and topic_tree (Leiden, in leiden.go). Both expose a uniform Hierarchy interface.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func LabelCommunity ¶
LabelCommunity computes a human-readable label using the 3-tuple heuristic from spec §5.5.4: "<dominant_pkg> — <common_substring>* + <top_pagerank_node>". `members` is the slice of nodes belonging to one community.
Types ¶
type LeidenOpts ¶
LeidenOpts controls a single run.
type PersistClusterEdge ¶
PersistClusterEdge mirrors persist.ClusterEdge so the buildpipe orchestrator can hand pkg-tree edges to persist.Store without forcing cluster to import persist (which would, via persist→cluster for TopicTree types, create an import cycle). Both types have identical fields.
type PkgTree ¶
type PkgTree struct {
Edges []Edge
// contains filtered or unexported fields
}
PkgTree captures the structural-depth hierarchy derived from package paths. level semantics:
- root pkg (no slash in qname) = 0
- each nested subpkg adds +1
- file = parent_pkg.level + 1
- decl (type/func/var) = file.level + 1
- LogicBlock = function.level + 1
IMPORTANT: this is structural depth, NOT the spec §5.4 L0..L4 LOD band. Deep monorepos (a/b/c/d package nesting) produce levels >4 (unbounded above: depth-N package nesting yields file at level N+1, function at level N+2, etc.). The viewer's LOD wiring (T23) must derive the LOD band from node.Type independently rather than reading PkgTree.level directly.
func BuildPkgTree ¶
BuildPkgTree derives the tree from node attributes (Type + FilePath). Logic block nodes inherit their function's level + 1.
func (*PkgTree) PersistEdges ¶
func (t *PkgTree) PersistEdges() []PersistClusterEdge
PersistEdges converts pkg_tree edges to the persist-friendly slice expected by persist.Store.InsertPkgTreeFromCluster.
type Resolution ¶
Resolution captures the partition produced at one γ value.
type TopicTree ¶
type TopicTree struct {
Resolutions []Resolution
// For convenience: per-node, the community ID at each resolution.
NodeToComm []map[string]int // index = resolution index
}
TopicTree holds Leiden communities at multiple resolutions.
func BuildTopicTree ¶
BuildTopicTree runs Leiden at each gamma in `gammas`, naming communities, then applies an adaptive split pass: communities exceeding `oversizedFraction` of the participant set, or low-cohesion communities over `diffuseMinSize`, get re-Leidened on their subgraph so the output stays readable on graphs where the first Leiden pass collapsed real subsystems together.
Meta nodes (Commit, Hunk — schema 1.4/1.8 G6 Temporal) are excluded from community participation per hunk-graph.md §11.7 (decision 2026-05-09). They have no semantic edges (no calls/invokes/references/etc.) so their inclusion would yield singleton communities that pollute the resolution without adding signal. Excluded nodes get NO entry in NodeToComm — viewer callers must treat absence as "no community" (matches the contract for any node the Leiden run drops).
func (*TopicTree) ResolutionGamma ¶
func (*TopicTree) ResolutionMembers ¶
func (*TopicTree) ResolutionsCount ¶
ResolutionsCount/ResolutionGamma/ResolutionMembers satisfy the persist.TopicTreeInput interface (declared in persist) so persist can consume a *TopicTree without importing cluster types directly at the interface boundary.
Source Files