internal/community/hierarchy.go
internal/community · 195 lines · 10 declarations · source
Declarations
const MaxSize
const MaxSize = 24
MaxSize is how many entities a group may hold before it is split again.
PROVISIONAL, like Resolution, and for the same reason. What it controls is whether a level exists at all: a bound larger than the biggest group means one level and no hierarchy, and a small one means levels of groups too small to have a theme. The number that is right depends on how much a summary can hold about a subject, which is a measurement nobody has taken here.
type Level
type Level int
Level is one depth of the hierarchy: zero is the partition over the whole graph.
type Community
type Community struct {
// ID is unique across the hierarchy. Assigned in level order and then by lowest member, so the
// same graph always produces the same identifiers.
ID int
Level Level
// Parent is the community this was split out of, or -1 at the root. Explicit rather than inferred
// from membership overlap: a walk that has to work out where it came from by comparing member
// sets gets it wrong the moment two siblings share nothing but their parent, and it does that
// work on every walk.
Parent int
// Members are entity identifiers, sorted.
Members []string
}
Community is one group at one level, with the group it was split out of.
type Hierarchy
type Hierarchy struct {
Communities []Community
}
Hierarchy is every community at every level.
Why there are levels at all
A question has a scale. "What is going on at work" and "what is going on with the migration" are both thematic and they are not the same question, and one partition answers one of them. A level exists exactly where a group was too large to be one subject and was split again — so the depth of the tree is a property of the memory rather than a number somebody chose.
var finer
var finer = []float64{2, 4, 8, 16}
finer is the ladder of densities a split tries, as multiples of the base.
Why a ladder rather than one multiplier
A group is split by asking a stricter question of it: how dense does a set of things have to be before it counts as one subject. How much stricter depends on the group — two subjects joined by a handful of relations come apart at barely above the base, and two joined by dozens need much more — and a single multiplier chosen once would divide the first group into fragments and leave the second whole.
So the split takes the COARSEST density that actually divides the group, which makes the multiplier a property of the group rather than a parameter. The ladder is short and bounded because past a point every set of things is its own subject, and a partition of singletons is not a split: it is the group saying it has no structure inside it.
func Build
func Build(g *Graph) Hierarchy
Build partitions a graph and splits any group too large to be one subject.
Splitting is a partition of the group alone
A group that is too large is re-partitioned over the subgraph induced on its own members, not over the whole graph again. Over the whole graph its members could leave for communities the parent does not contain, and the result would not be a refinement of the parent — which is what makes the tree a tree rather than a set of unrelated partitions stacked on top of each other.
A split that does not split stops
A group whose partition is itself — dense enough that nothing improves by dividing it — is left alone even though it is over the bound. The alternative is dividing it arbitrarily, which produces two summaries of half a subject each and no way to tell that is what happened.
method Hierarchy.Depth
func (h Hierarchy) Depth() int
Depth is how many levels the hierarchy has.
func namesOf
func namesOf(g *Graph, members []int) []string
func split
func split(sub *Graph) (Partition, bool)
split finds the coarsest density that divides a group into subjects.
A partition of singletons is rejected rather than accepted as a split: it means the density has been raised past the point where anything is a group, and dividing a subject into its individual members is not a finer view of it. A group that only ever shatters is one with no structure inside — a set of things all equally connected to each other — and it stays whole.
func allSingletons
func allSingletons(p Partition) bool