README
¶
meso
meso is a pure-Go, deterministic community-detection library. It recovers the
mesoscale structure of a weighted graph, the level between individual nodes and
the whole network, using the Leiden algorithm (Traag, Waltman, van Eck, 2019)
with Louvain as its baseline.
See docs/meso-design.md for the design of record.
Goals
- A faithful, best-in-class Leiden implementation, with Louvain as the baseline and a shared quality-function core.
- Bit-reproducible output for a given input, seed, and parameters, including under parallelism.
- Idiomatic, dependency-free public API with an optional gonum adapter.
Modules
github.com/andreswebs/meso- the dependency-free core.github.com/andreswebs/meso/gonum- an optional adapter to gonum's graph types, shipped as a separate nested module so the core never pulls gonum into consumers that do not want it.
Development
All commands run from the project root via make; see make help. The full
quality gate is make validate (fmt-check, vet, lint, test) across every
module.
Authors
Andre Silva - @andreswebs
License
This project is licensed under the GPL-3.0-or-later. Linking meso
makes the importing program a derivative work that must itself be GPLv3-
compatible.
Documentation
¶
Overview ¶
Package meso is a pure-Go, deterministic community-detection library.
meso recovers the mesoscale structure of a weighted graph, the level between individual nodes and the whole network, using the Leiden algorithm (Traag, Waltman, van Eck, 2019) with Louvain as its baseline. Output is bit- reproducible for a given input, seed, and parameters, including under parallelism.
The core is dependency-free. An optional gonum adapter ships as a separate nested module, github.com/andreswebs/meso/gonum, so importers who do not want gonum never pull it in.
A Builder is the entry point: it maps arbitrary caller keys to dense node indices, accepts weighted edges and optional node weights, and folds self-loops and parallel edges into edge weights, producing an immutable Graph.
g, err := meso.NewBuilder().
AddEdge("a", "b", 1.0).
AddEdge("b", "c", 2.0).
Build()
Leiden and Louvain consume a Graph and return a Result with the detected communities (keyed by the caller's keys) and the achieved quality. The objective, resolution, and seed are set through options.
res, err := meso.Leiden(g, meso.WithQuality(meso.Modularity(1.0)), meso.WithSeed(42)) // res.Communities(), res.Quality()
A run is byte-identical for a given graph, options, and seed.
Directed graphs are supported. Build one with NewDirectedBuilder, where AddEdge(from, to, w) records an arc from -> to, and optimise it with DirectedModularity, the Leicht-Newman directed objective whose null model credits an arc against its source's out-strength and its target's in-strength. A directed graph must be run with DirectedModularity: the undirected Modularity and CPM null models mis-score directed arcs and are rejected. On a symmetric graph DirectedModularity reduces to Modularity. CPM stays undirected by design.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func AMI ¶
AMI returns the adjusted mutual information of partitions a and b: their mutual information corrected for chance against the expected value under the permutation model, then normalized by the arithmetic mean of their entropies (Vinh et al., 2010). It is 1 for identical partitions (up to relabeling), about 0 for independent partitions, and can be negative. Unlike NMI it is safe to compare across different numbers of communities. a and b must have the same length; AMI panics otherwise.
AMI = (MI - E[MI]) / ((H(a) + H(b))/2 - E[MI])
When both partitions are a single community the value is defined as 1. Near a degenerate denominator the divisor is clamped to the smallest normal-scale epsilon, as in scikit-learn, so the result stays finite.
func ARI ¶
ARI returns the adjusted Rand index of partitions a and b, the pair-counting agreement corrected for chance (Hubert and Arabie, 1985). It is 1 for identical partitions (up to relabeling), about 0 for independent partitions, and can be negative when agreement is below chance. a and b must have the same length; ARI panics otherwise.
ARI = (sum_ij C(n_ij,2) - E) / (0.5*(sum_i C(a_i,2) + sum_j C(b_j,2)) - E) E = sum_i C(a_i,2) * sum_j C(b_j,2) / C(n,2)
where n_ij is the contingency count and a_i, b_j the per-label totals. When the denominator is zero (both partitions are trivial in the same way, for example all-singletons vs all-singletons) the value is defined as 1.
func NMI ¶
NMI returns the normalized mutual information of partitions a and b: their mutual information divided by the arithmetic mean of their entropies. It is 1 for identical partitions (up to relabeling) and 0 when they share no information. Note NMI is not adjusted for chance, so independent partitions score above 0 on average; use AMI when a chance-corrected score is needed. a and b must have the same length; NMI panics otherwise.
NMI = MI(a, b) / ((H(a) + H(b)) / 2)
When both partitions are a single community (both entropies zero) the value is defined as 1, matching the identical-partition case.
Types ¶
type Builder ¶
type Builder struct {
// contains filtered or unexported fields
}
Builder is the public entry point for constructing a Graph from caller data. It maps arbitrary string keys to dense node indices in first-seen order, accumulates weighted edges (folding parallel edges and self-loops), and records optional node weights. Build produces the immutable Graph.
A Builder is not safe for concurrent use. Its methods return the Builder so calls can be chained; input validation is deferred to Build, which returns the first error encountered.
func NewDirectedBuilder ¶
func NewDirectedBuilder() *Builder
NewDirectedBuilder returns a Builder for a directed graph. The resulting Graph keeps in-arcs and out-arcs separable (the foundation for directed modularity in M3); AddEdge(from, to, w) records an arc from -> to.
func (*Builder) AddEdge ¶
AddEdge adds a weighted edge between from and to. Repeated calls on the same endpoint pair sum their weights into a single edge; for an undirected builder the pair is unordered, for a directed builder the arc from -> to is distinct from to -> from. A self-loop (from == to) is recorded as node-internal weight rather than a neighbour entry. Both endpoints are registered as nodes.
A negative or NaN weight is rejected: Build will return an error.
func (*Builder) AddNodeWeight ¶
AddNodeWeight sets the node weight (size) of key, registering it as a node if unseen. Nodes without an explicit weight default to size 1.0. A negative or NaN size is rejected: Build will return an error.
func (*Builder) Build ¶
Build validates the accumulated input and produces the immutable Graph. It returns an error if any edge or node weight was negative or NaN. Degenerate inputs (empty, single node, isolated nodes, disconnected components) build a valid graph.
func (*Builder) Canonical ¶
Canonical makes Build assign dense node indices by ascending caller key rather than first-seen order, so the resulting Graph is a pure function of the key set and edge weights - independent of the order edges were inserted. This is the order-independence half of the determinism model (design section 4.4): two callers who insert the same edges in different orders get byte-identical models and therefore identical partitions. It returns the Builder for chaining and must be set before Build.
type Graph ¶
type Graph struct {
// contains filtered or unexported fields
}
Graph is the immutable weighted graph produced by a Builder. It wraps the internal CSR model over dense indices [0, n) together with the reverse index-to-key mapping needed to round-trip community labels back to the caller's keys.
type Option ¶
type Option func(*runConfig)
Option configures a Leiden or Louvain run. Options are applied in order over a default configuration (modularity at resolution 1, seed 0); a later option overrides an earlier one.
func WithIterations ¶
WithIterations sets the number of full Leiden passes to run. Each pass after the first restarts from the previous pass's partition with fresh refinement randomness derived from the seed, so quality never decreases with more passes and runtime grows linearly with the count. The default is 1; a count below 1 is rejected. Louvain has no refinement randomness and ignores this option.
The reason to set a count above 1: a single Leiden pass can return communities that still admit a strictly improving split. Refinement only re-divides the communities found within a pass, so a community assembled across aggregation levels is never re-examined at node granularity; reference implementations exhibit the same per-run behaviour. The Leiden paper's subset-optimality guarantee is asymptotic over repeated randomized iterations, which is what extra passes supply. More passes reduce, but never eliminate, the chance of such partitions.
func WithParallelism ¶
WithParallelism runs the fast local-move phase in the synchronous-round parallel mode (design section 4.5) using the given number of worker goroutines; a value <= 0 means one worker per available core (runtime.GOMAXPROCS). The output is byte-identical regardless of the worker count - the round decides every move from the round-start snapshot and applies them in a fixed order - so parallelism buys speed without sacrificing reproducibility. Without this option a run is serial.
Synchronous rounds reach a different local-move fixed point than the default serial phase, so a parallel run's partition may differ from the serial run's on the same input; both are valid community assignments. A run is a pure function of (graph, options), and with a fixed seed byte-identical across machines and core counts.
func WithQuality ¶
func WithQuality(q QualityFunction) Option
WithQuality selects the quality function to optimise, such as Modularity or CPM. The default is Modularity(1.0).
func WithResolution ¶
WithResolution overrides the resolution parameter gamma of the selected quality function, without rebuilding it: WithQuality(Modularity(1.0)) together with WithResolution(2.0) optimises modularity at gamma 2.0. Higher gamma favours smaller communities.
type Partition ¶
type Partition []int
Partition assigns each node a community label: the label of node i is p[i]. It is the Go realization of the Lean Partition n := Fin n -> Nat (see verification/lean/Meso/Graph.lean and verification/lean/CORRESPONDENCE.md).
Lean encodes well-formedness structurally, as a total function on Fin n; in Go it is the length-and-range check of wellFormed: a partition of n nodes has length n and every label in [0, n), since n nodes form at most n communities.
type QualityFunction ¶
QualityFunction scores a partition of a graph: higher is better. It is the objective the optimizers (Louvain, Leiden) maximize, and the single shape shared by modularity, CPM, and directed modularity so the move loop can be written once against the interface.
Quality is the full from-scratch evaluation of the objective over the whole graph. It is deliberately simple and slow (the O(n^2) double sum for modularity), so it is obviously correct and serves as the oracle the incremental move-delta is property-checked against. The method takes the internal csr, so quality functions are meso-internal; callers select one through constructors such as Modularity.
func CPM ¶
func CPM(gamma float64) QualityFunction
CPM returns the Constant Potts Model quality function with resolution parameter gamma. Where modularity penalises a within-community pair by a degree-based, graph-size-dependent null model (gamma*k_i*k_j/2m), CPM penalises it by a flat node-size term gamma*s_i*s_j with no 2m normalisation. Gamma is therefore an absolute internal-density threshold: a community is worth keeping only while its internal weight exceeds gamma times its squared size (see [IsGammaDense]-style reasoning), and higher gamma favours smaller communities.
func DirectedModularity ¶
func DirectedModularity(gamma float64) QualityFunction
DirectedModularity returns the Leicht-Newman directed modularity quality function with resolution parameter gamma. It is the directed analogue of Modularity: the null model uses each pair's separate out- and in-degrees (k_i^out * k_j^in / m) rather than the symmetric k_i * k_j / 2m, so an arc i -> j is credited against i's out-strength and j's in-strength.
It reads the directed CSR's separable out- and in-adjacencies (see [csr]). On an undirected graph, where in-degree equals out-degree and the total m equals 2m, it reduces exactly to Modularity. Gamma scales the null-model term as in Modularity.
Unlike modularity and CPM, directed modularity has no Lean model: directed support is a deliberate descope (the Lean weight-symmetry assumption is load-bearing), so its correctness rests on the directed reference oracle, not a proof.
func Modularity ¶
func Modularity(gamma float64) QualityFunction
Modularity returns the modularity quality function with resolution parameter gamma. Gamma scales the null-model (expected-weight) term: gamma = 1 is classical modularity, higher gamma favours smaller communities and lower gamma favours larger ones.
type Result ¶
type Result struct {
// contains filtered or unexported fields
}
Result is the outcome of a community-detection run: the community each node was assigned to, and the achieved quality. Communities are reported in the caller's keys via the source Graph's reverse index.
func Leiden ¶
Leiden runs the Leiden algorithm (Traag, Waltman, van Eck, 2019) on g and returns the detected communities and achieved quality. It optimises the quality function chosen by WithQuality (modularity at resolution 1 by default), using the seed from WithSeed for refinement randomness, so the result is byte-identical for a given graph, options, and seed.
A directed graph must be run with DirectedModularity (build it with NewDirectedBuilder); any other quality function is rejected because its null model mis-scores directed arcs.
func Louvain ¶
Louvain runs the Louvain algorithm (local moving plus aggregation, no refinement) on g and returns the detected communities and achieved quality. It is the deterministic baseline Leiden layers refinement on: it optimises the WithQuality objective (modularity at resolution 1 by default) and, having no randomness, ignores WithSeed.
As with Leiden, a directed graph must be run with DirectedModularity; any other quality function is rejected.
func (*Result) Communities ¶
Communities returns the community label of every node, keyed by the caller's original key. Two keys share a label exactly when their nodes are in the same community; labels are dense indices in [0, number of communities).
Source Files
Directories