internal/community/graph.go
internal/community · 260 lines · 10 declarations · source
This file carries the package documentation, rendered on the package page.
Declarations
type Edge
type Edge struct {
Source string
Target string
Weight float64
}
Edge is an asserted relation between two entities, with how much it should count.
Weight is a count rather than a strength: two people connected by four relations are more connected than two joined by one, and nothing here judges which relation matters more. A judgement about that would be a ranking stage, and it would have to be justified by a measurement it improves.
type Graph
type Graph struct {
// names holds the entity identifiers in sorted order. An index into this slice is how a node is
// named everywhere else, so every loop over nodes is a loop in a fixed order.
names []string
index map[string]int
// adjacency[i] holds i's neighbours. Each edge appears in both endpoints' lists.
adjacency [][]neighbour
}
Graph is an undirected weighted graph over entity identifiers.
Why direction is dropped
The relations are directed and the grouping is not. "Hamza manages Marta" and "Marta reports to Hamza" are the same connection seen from two ends, and counting them as two edges would make a pair of people look twice as connected as they are — which is a difference the partition acts on.
Why it is built rather than accepted
Determinism is a property of this package, and it starts here: the same set of edges in a different order has to produce the same graph, so identifiers are sorted and given indices, duplicates are summed rather than repeated, and self-loops are kept out. A partition built over an adjacency list whose order depended on the caller's iteration order would be stable in tests and unstable in production, which is the worst combination.
type neighbour
type neighbour struct {
node int
weight float64
}
func NewGraph
func NewGraph(edges []Edge) (*Graph, error)
NewGraph builds an undirected graph from asserted relations.
Edges naming the same pair are summed. An edge from something to itself is dropped: a self-loop contributes to no grouping decision, because a node is already in its own community, and carrying one would distort the strength that every move is measured against.
method Graph.Order
func (g *Graph) Order() int
Order is how many entities the graph holds.
method Graph.Name
func (g *Graph) Name(node int) string
Name returns the identifier of a node.
method Graph.Neighbours
func (g *Graph) Neighbours(node int) []int
Neighbours returns the nodes one node is connected to, in a fixed order.
Exported so a caller can walk the graph the partition was made over — which is what a test asserting that a group is internally connected has to do, and what anything checking a chain against the graph would do. It exposes the shape, never the weights: a weight is an input to a grouping decision and nothing outside this package makes one.
method Graph.Components
func (g *Graph) Components() [][]int
Components returns the connected components, each as a sorted list of node indices.
Why every component is kept
A corpus of documents about one subject has a giant component with noise around it, so clustering only the largest is a reasonable simplification there. A person's memory is not shaped like that: work, family, a hobby and a trip share no entity at all and are components of similar weight. Keeping only the largest would silently drop most of somebody's life, and the loss would be invisible — the answers that remained would look fine.
They are returned separately because partitioning them together is wasted work: no move between components can ever improve anything, since there is no edge to gain.
method Graph.Subgraph
func (g *Graph) Subgraph(nodes []int) (*Graph, []int)
Subgraph returns the graph induced on a set of nodes, and a mapping back to this graph's indices.
Used to split a group that was too large to be one subject: the split is a partition of the group alone, and running it over the whole graph again would let members leave for communities the parent does not contain.
method Graph.Isolated
func (g *Graph) Isolated(nodes []int, kept []int) []int
Isolated returns the members of a node set that the induced subgraph does not contain.
These are the members whose every edge left the group. They are not noise and they are not dropped: each is a group of one, which is what a thing connected only to other subjects is.