internal/community/leiden.go
internal/community · 477 lines · 20 declarations · source
Declarations
const Resolution
const Resolution = 0.05
Resolution is how dense a group has to be to be one subject.
PROVISIONAL, and it must not be read as anything else — #102 holds what would settle it. Set too low it produces a handful of enormous groups, each summarised as though it were one subject; too high, dozens too small to have a theme. Both return answers and neither looks wrong from outside, which is exactly why the number needs a measurement against a real scope rather than a plausible default.
func quality
func quality(internal, size, resolution float64) float64
quality scores a group by internal weight against how dense a group of that size has to be.
Why density against a resolution, and not modularity
Modularity compares a group's internal edges against what a random graph with the same degrees would hold, and that comparison has a resolution limit: below a size that depends on how big the WHOLE graph is, a genuine small group is always better merged into a neighbour. The same subject — four entities, densely joined — would be kept in a small scope and dissolved in a large one, and the dissolving would happen as somebody's memory grew. A retrieval surface that degrades with use is the failure mode that cannot be found in testing, because testing is done on small inputs.
Density is local: a group's fate depends on the group, so nothing about it changes when unrelated memory is added elsewhere. It also makes the parameter a number somebody can reason about — how connected a set of things has to be before it is a subject — rather than one whose meaning moves.
type Partition
type Partition struct {
// Of[node] is the group a node belongs to. Group numbers are contiguous from zero, assigned in
// order of each group's lowest member, so the same partition always carries the same numbers.
Of []int
// Groups holds each group's members, sorted, indexed by group number.
Groups [][]int
}
Partition is an assignment of every node to a group.
func Detect
func Detect(g *Graph) Partition
Detect partitions a graph into the subjects it contains, at the default density.
func DetectAt
func DetectAt(g *Graph, resolution float64) Partition
DetectAt partitions at a stated density, which is what a level of the hierarchy varies.
A subject at one scale is several at a finer one — "work", and inside it "the migration" — and the only difference between those two answers is how dense a set of things has to be before it counts as one subject. Splitting a group by running the SAME density over it again returns it whole, which is no surprise: that density is what chose the group.
Three phases, and each is there for a different reason
**Moving** takes each node to whichever group its presence improves most, in a fixed order, until nothing moves. A node is only considered for a group it has an edge to: a move into a group it does not touch cannot improve density and would put a thing into a subject it has nothing to do with.
**Splitting** breaks every group into its connected pieces. Moving alone can leave a group internally disconnected — a node that joined early can be the only thing holding two halves together, and when it later moves away nothing puts them back, because each half is already where it wants to be. That group is two subjects with one name, and whatever summarises it writes one summary about two things. Splitting makes connectedness a property of the output rather than a hope, and it needs no parameter and no randomness.
**Aggregating** collapses each group to a single node and starts again. This is not an optimisation: moving can only relocate one node at a time, so it can NEVER merge two groups, however much merging them would improve. Two dense subjects joined by sixteen relations stay separate at every density without this — measured, on exactly that graph. Aggregation is what makes a merge a single move.
Why there is no randomness
The published form of this algorithm makes the splitting phase a randomised search for sub-communities, which both guarantees connectedness and helps escape the arrangement the first pass settles in. Only the first is a correctness property, and taking it directly — split into connected pieces — makes it a property of the code. That removes the determinism problem rather than solving it: there is no generator to pin, no stream a toolchain upgrade can change, and no way for a scope's themes to reorganise between two runs of the same input.
What it costs is the escape from local optima. The day a measurement says the partition is worse than it should be, a randomised refinement is what to add — and determinism stops being free at that point, so it will need a generator whose stream is fixed by its own definition.
Components are partitioned independently
No move can cross between two parts of the graph with no edge between them, so partitioning them together is wasted work — and keeping only the largest, which suits a document corpus, would silently discard most of a person's memory: work, family, a hobby and a trip share no entity at all.
type tier
type tier struct {
graph *Graph
// size[i] is how many original entities node i stands for, and internal[i] is the weight of the
// edges already inside it. Both are needed by the quality function, which is about a set of
// entities rather than about a node.
size []float64
internal []float64
// members[i] lists the original node indices behind node i.
members [][]int
}
tier is one level of aggregation: a graph whose nodes stand for groups of the original.
func partitionComponent
func partitionComponent(g *Graph, component []int, membership []int, resolution float64)
partitionComponent runs moving, splitting and aggregating over one connected component, writing the result into membership in the original graph's coordinates.
Membership is written on every round rather than only at the end, so the answer is complete whichever round turns out to be the last.
func seedTier
func seedTier(g *Graph, component []int) (tier, bool)
seedTier is the starting point: every entity alone.
Starting from singletons rather than from one group means the first pass builds subjects up rather than carving them out, and a thing that belongs nowhere stays alone rather than having to escape.
func move
func move(t tier, nodes []int, membership []int, resolution float64)
move takes each node to the group it does most good in, until nothing moves.
Nodes are visited in index order, which is sorted label order. The visit order changes the outcome, so it has to be fixed rather than whatever order the caller supplied edges in.
func gainOfJoining
func gainOfJoining(internal, size, links float64, t tier, node int, resolution float64) float64
gainOfJoining is what one node adds to a group by being in it, counting what it already holds.
func splitDisconnected
func splitDisconnected(g *Graph, nodes []int, membership []int)
splitDisconnected breaks every group into its connected pieces.
The guarantee. A group that is two pieces joined by nothing is two subjects with one name, and everything downstream treats it as one. A piece keeps the lowest node in it as its label, so the same split always produces the same labels.
func reachableWithin
func reachableWithin(g *Graph, start int, inGroup map[int]bool, seen map[int]bool) []int
reachableWithin walks the part of a group reachable from one member without leaving it.
func aggregate
func aggregate(t tier, groups [][]int) (tier, error)
aggregate collapses each group into one node, carrying what is already inside it.
The internal weight and the size travel with the node, which is what lets the next round judge a merge of two groups by the same rule it judged a move of one entity: a group is a set of entities, and the quality function only ever asked about sets.
func groupsOf
func groupsOf(membership []int) [][]int
groupsOf collects a membership into groups, each sorted, ordered by lowest member.
func finalise
func finalise(g *Graph, membership []int) Partition
finalise renumbers groups so a partition does not carry node indices as labels.
Numbered by each group's lowest member, so two runs over one graph produce the same grouping AND the same numbers — which anything storing a group id depends on, and which makes a determinism test an equality rather than a comparison of set contents.
func linksToGroups
func linksToGroups(g *Graph, membership []int, node int) map[int]float64
linksToGroups sums the weight from one node into each group it touches.
func label
func label(i int) string
label and unlabel name an aggregate node.
Zero-padded, because a graph sorts its nodes by name and "10" sorts before "2". Unpadded labels would make the aggregate graph's node order depend on how many groups there are, which is a different partition for the same input.
func unlabel
func unlabel(s string) int
func sortedKeys
func sortedKeys(m map[int]float64) []int
sortedKeys and sortedIntKeys exist because Go randomises map iteration deliberately, and the order groups are considered in decides which of two equally good moves is taken.
func sortedIntKeys
func sortedIntKeys(m map[int][]int) []int