Documentation
¶
Overview ¶
Package centrality implements vertex importance metrics. v1 carries Brandes' betweenness centrality and the PageRank family (T61/T62 sister tasks).
Index ¶
- Variables
- func Betweenness[W any](c *csr.CSR[W]) []float64
- func BetweennessCtx[W any](ctx context.Context, c *csr.CSR[W]) ([]float64, error)
- func BetweennessParallel[W any](c *csr.CSR[W], numWorkers int) []float64
- func BetweennessParallelCtx[W any](ctx context.Context, c *csr.CSR[W], numWorkers int) ([]float64, error)
- func Closeness[W any](c *csr.CSR[W]) []float64
- func ClosenessCtx[W any](ctx context.Context, c *csr.CSR[W]) ([]float64, error)
- func Eigenvector[W any](c *csr.CSR[W], opts EigenvectorOptions) ([]float64, int, error)
- func EigenvectorCtx[W any](ctx context.Context, c *csr.CSR[W], opts EigenvectorOptions) ([]float64, int, error)
- func Harmonic[W any](c *csr.CSR[W]) []float64
- func HarmonicCtx[W any](ctx context.Context, c *csr.CSR[W]) ([]float64, error)
- func Katz[W any](c *csr.CSR[W], opts KatzOptions) ([]float64, int, error)
- func KatzCtx[W any](ctx context.Context, c *csr.CSR[W], opts KatzOptions) ([]float64, int, error)
- func PageRank[W any](c *csr.CSR[W], opts PageRankOptions) (ranks []float64, iterations int, err error)
- func PageRankCtx[W any](ctx context.Context, c *csr.CSR[W], opts PageRankOptions) (ranks []float64, iterations int, err error)
- func PersonalisedPushPageRank[W any](c *csr.CSR[W], src graph.NodeID, opts PPRPushOptions) ([]float64, error)
- func PersonalisedPushPageRankCtx[W any](ctx context.Context, c *csr.CSR[W], src graph.NodeID, opts PPRPushOptions) ([]float64, error)
- func WeightedBetweenness(c *csr.CSR[float64]) ([]float64, error)
- func WeightedBetweennessCtx(ctx context.Context, c *csr.CSR[float64]) ([]float64, error)
- func WeightedBetweennessParallel(c *csr.CSR[float64], numWorkers int) ([]float64, error)
- func WeightedBetweennessParallelCtx(ctx context.Context, c *csr.CSR[float64], numWorkers int) ([]float64, error)
- type EigenvectorOptions
- type KatzOptions
- type PPRPushOptions
- type PageRankOptions
- type PageRanker
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrInvalidInput = errors.New("centrality: input option is invalid (NaN, Inf, or out of range)")
ErrInvalidInput is returned by centrality algorithms when their float options contain an invalid value: NaN, +/-Inf, or an out-of-range parameter (e.g. Damping outside (0,1), negative Tolerance/Epsilon). Non-finite or out-of-range inputs propagate through the power-iteration and push loops and silently corrupt the rank vector; validating once at entry is mandatory.
var ErrMaxStepsExceeded = errors.New("centrality: MaxSteps budget exhausted before convergence")
ErrMaxStepsExceeded is returned by PersonalisedPushPageRank and PersonalisedPushPageRankCtx when the MaxSteps budget is reached before the residue converges to Epsilon. The returned rank vector is the partial result accumulated so far and does NOT satisfy the ε-approximation guarantee.
var ErrNonPositiveWeight = errors.New("centrality: edge weight must be strictly positive")
ErrNonPositiveWeight is returned by WeightedBetweenness and WeightedBetweennessCtx when any edge weight is zero or negative. Brandes' weighted variant builds a predecessor DAG ordered by shortest-path distance using Dijkstra; zero-weight edges connect two nodes at equal distance, which can cause a node to be settled (and its σ consumed downstream) before a later-settled equal-distance predecessor has accumulated its contribution — making σ inconsistent and silently corrupting the centrality values. Strictly positive weights are therefore required.
Functions ¶
func Betweenness ¶
Betweenness computes the exact betweenness centrality of every node in c using Brandes' algorithm (2001). Returns a slice indexed by NodeID. Unweighted: O(V * E).
The result is not normalised — callers can divide by (n-1)(n-2) for the classical normalised score. This same divisor applies whether c is directed or undirected: Brandes' source loop runs over every vertex regardless of orientation, so the raw output is already on an ordered-pair basis for both (an undirected edge is walked in both directions during the shortest-path search). Dividing an undirected result by (n-1)(n-2)/2 instead double-counts and can push the normalised score above 1.0 — see WeightedBetweenness, which uses the same uniform 1/((n-1)(n-2)) factor.
Example ¶
ExampleBetweenness computes (non-normalised) betweenness centrality on an undirected path 0-1-2. Every shortest path between the two ends runs through the middle node, so node 1 carries all the betweenness while the endpoints carry none.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph/adjlist"
"github.com/FlavioCFOliveira/GoGraph/graph/csr"
"github.com/FlavioCFOliveira/GoGraph/search/centrality"
)
func main() {
// Undirected path: 0 - 1 - 2.
a := adjlist.New[int, struct{}](adjlist.Config{Directed: false})
_ = a.AddEdge(0, 1, struct{}{})
_ = a.AddEdge(1, 2, struct{}{})
c := csr.BuildFromAdjList(a)
m := a.Mapper()
bc := centrality.Betweenness(c)
for v := 0; v < 3; v++ {
id, _ := m.Lookup(v)
fmt.Printf("node %d betweenness = %.1f\n", v, bc[id])
}
}
Output: node 0 betweenness = 0.0 node 1 betweenness = 2.0 node 2 betweenness = 0.0
func BetweennessCtx ¶
BetweennessCtx is the context-aware variant of Betweenness. ctx.Err() is checked once per source vertex; on cancellation returns (nil, wrapped ctx.Err()).
func BetweennessParallel ¶
BetweennessParallel computes the exact (unweighted) betweenness centrality of every NodeID in c using the Brandes algorithm parallelised across sources. Each worker goroutine processes a disjoint range of source vertices, accumulating into its own private centrality buffer; the final reduction sums these buffers into the returned slice.
Output is deterministic for a fixed numWorkers value. Due to non-associative floating-point addition, the result may differ from Betweenness by up to ~1e-12 per node when numWorkers > 1; the two agree within this numerical tolerance. For exact bit-identity with the serial result, use Betweenness directly.
numWorkers <= 0 picks runtime.GOMAXPROCS(0). For tiny graphs (V below ~1024) the parallel overhead dominates and the serial Betweenness is preferable.
func BetweennessParallelCtx ¶
func BetweennessParallelCtx[W any](ctx context.Context, c *csr.CSR[W], numWorkers int) ([]float64, error)
BetweennessParallelCtx is the context-aware variant of BetweennessParallel. ctx cancellation is checked once per source vertex inside every worker; on cancellation returns (nil, wrapped ctx.Err()).
func Closeness ¶ added in v0.6.0
Closeness computes closeness centrality over the immutable snapshot c, returning a per-NodeID slice of length c.MaxNodeID().
The score uses the Wasserman-Faust normalisation, which is well-behaved on disconnected graphs (the classic 1/Σd form over-rewards nodes trapped in a small component). For a node u that reaches r other nodes at total distance Σd over the n nodes of the graph:
C(u) = (r / (n-1)) * (r / Σd)
A node that reaches no other node (Σd == 0, including every node with no outgoing edges and every isolated node) scores exactly 0 — never NaN/Inf.
Orientation: distances are measured along OUTGOING edges (how quickly u can reach the rest of the graph). For the incoming convention (how quickly u is reached, the NetworkX default) pass c.BuildReverse(). On an undirected (symmetric) snapshot the two are identical. Self-loops and parallel edges do not affect any shortest-path distance and are therefore ignored.
Complexity is O(V*(V+E)) — one breadth-first search per source. Concurrency: Closeness allocates its own buffers per call and is safe to invoke from any number of goroutines on a snapshot CSR.
Reference: Wasserman & Faust, Social Network Analysis (1994), ch. 5; Freeman, Social Networks 1 (1978/79) 215-239.
func ClosenessCtx ¶ added in v0.6.0
ClosenessCtx is the context-aware variant of Closeness. ctx.Err() is checked at every source-node boundary; on cancellation it returns (nil, wrapped ctx.Err()).
func Eigenvector ¶ added in v0.6.0
Eigenvector computes eigenvector centrality over the immutable snapshot c by power iteration, returning an L2-normalised per-NodeID slice of length c.MaxNodeID().
A node's score is proportional to the sum of its neighbours' scores — the dominant eigenvector of the adjacency matrix. The iteration uses the NetworkX recurrence x ← x + A·x (equivalently power iteration on I+A), which shares A's dominant eigenvector but, unlike plain power iteration, converges on bipartite graphs (stars, paths, even cycles) instead of oscillating.
Orientation: a node accumulates the scores of its IN-neighbours (predecessors) — the left dominant eigenvector, matching NetworkX. For the out-edge variant pass c.BuildReverse(). On an undirected snapshot the two coincide. Self-loops (diagonal of A) and parallel edges (edge multiplicity) are preserved and DO affect the result, as the measure is defined on A.
Caveats (Perron-Frobenius): a unique strictly-positive eigenvector is guaranteed only on a strongly-connected (irreducible) graph. On a disconnected graph the vector concentrates on the dominant component and is ~0 elsewhere; on a directed acyclic graph the measure is degenerate (use Katz or PageRank). An edgeless graph has no eigenvector structure and yields all-zero scores. If the iteration does not converge within MaxIterations, Eigenvector returns ErrMaxStepsExceeded (never a half- converged iterate).
Concurrency: Eigenvector allocates its own buffers per call and is safe for concurrent use on a snapshot CSR.
Reference: Bonacich, J. Math. Sociology 2 (1972) 113-120.
func EigenvectorCtx ¶ added in v0.6.0
func EigenvectorCtx[W any](ctx context.Context, c *csr.CSR[W], opts EigenvectorOptions) ([]float64, int, error)
EigenvectorCtx is the context-aware variant of Eigenvector. ctx.Err() is checked at every iteration boundary.
func Harmonic ¶ added in v0.6.0
Harmonic computes harmonic centrality over the immutable snapshot c, returning a per-NodeID slice of length c.MaxNodeID().
Harmonic centrality sums the reciprocal distance to every other node, with unreachable nodes contributing 0 (1/∞):
H(u) = ( Σ_{v ≠ u} 1/d(u,v) ) / (n-1)
Unlike closeness it is well-defined on every graph — disconnected, with isolated nodes, or directed — because an unreachable pair contributes a finite 0 rather than forcing a division by an infinite total. The result is normalised by n-1 so it lies in [0,1].
Orientation: distances are measured along OUTGOING edges (how quickly u can reach others). For the incoming convention pass c.BuildReverse(); on an undirected snapshot the two coincide. Self-loops and parallel edges do not affect shortest-path distances and are ignored.
Complexity is O(V*(V+E)) — one breadth-first search per source. Concurrency: Harmonic allocates its own buffers per call and is safe for concurrent use on a snapshot CSR.
Reference: Boldi & Vigna, "Axioms for Centrality", Internet Mathematics 10 (2014) 222-262; Rochat (2009); Marchiori & Latora (2000).
func HarmonicCtx ¶ added in v0.6.0
HarmonicCtx is the context-aware variant of Harmonic. ctx.Err() is checked at every source-node boundary; on cancellation it returns (nil, wrapped err).
func Katz ¶ added in v0.6.0
Katz computes Katz centrality over the immutable snapshot c, returning an L2-normalised per-NodeID slice of length c.MaxNodeID().
Katz centrality is the fixed point x = α·Aᵀ·x + β·1: a node's score is a baseline β plus α times the attenuated scores reaching it along incoming paths. The β baseline gives every node a non-zero floor, so — unlike Eigenvector — Katz is well-defined on disconnected graphs and directed acyclic graphs.
Orientation: a node accumulates the attenuated scores of its IN-neighbours (left eigenvector, matching NetworkX). For the out-edge variant pass c.BuildReverse(); on an undirected snapshot the two coincide. Self-loops and parallel edges are taken from A and DO affect the result.
Alpha must keep the series convergent (Alpha < 1/λ_max); see KatzOptions for the auto-selected safe default. If the iteration does not converge within MaxIterations, Katz returns ErrMaxStepsExceeded.
Representation note: Katz scores only participating nodes (≥1 incident edge). The immutable CSR cannot tell a genuinely isolated node from an unused slot in the sharded NodeID space, so isolated/ghost slots receive 0 rather than the textbook β floor — consistent with PageRank and Eigenvector.
Concurrency: Katz allocates its own buffers per call and is safe for concurrent use on a snapshot CSR.
Reference: Katz, L., Psychometrika 18 (1953) 39-43.
func KatzCtx ¶ added in v0.6.0
KatzCtx is the context-aware variant of Katz. ctx.Err() is checked at every iteration boundary.
func PageRank ¶
func PageRank[W any](c *csr.CSR[W], opts PageRankOptions) (ranks []float64, iterations int, err error)
PageRank runs the in-memory power-iteration form of PageRank over c and returns the per-NodeID rank slice plus the iteration count to convergence (capped at MaxIterations).
The returned slice has length c.MaxNodeID(); only NodeIDs that participate in at least one edge (live nodes) carry non-zero rank. The sum over the slice equals 1.0 within numerical tolerance.
Concurrency: PageRank is safe to invoke from any number of goroutines on a snapshot CSR; the function allocates its working buffers per call and does not share state.
Algorithm. The implementation is the textbook power-iteration form with proper handling of dangling nodes (nodes with out-degree 0): at each iteration the mass currently held by dangling nodes is redistributed uniformly across all live nodes, modelling them as teleporting their entire share back into the system. This ensures total mass is conserved and the result is a true stationary distribution.
Parallelism. On graphs with at least pageRankParallelThreshold live nodes and when GOMAXPROCS > 1, the per-iteration sparse mat-vec runs the pull formulation (next[v] = baseShare + d·Σ_{u∈in(v)} cur[u]/ outdeg[u]) over a reverse-CSR, partitioned across a persistent worker pool by approximately equal in-edge count. Each next[v] is computed independently with no write contention, and every vertex sums its in-edges in the fixed reverse-CSR order, so the result is bit-for-bit identical to the serial path regardless of GOMAXPROCS or worker scheduling. Smaller graphs use the serial push form unchanged and pay neither the reverse-CSR transpose nor any goroutine overhead.
Example ¶
ExamplePageRank ranks the nodes of a directed star where five leaves all point at one sink. The sink accumulates the dominant share of the stationary mass; the five leaves are symmetric and share the remainder equally. Ranks are rounded to four decimals for a stable, deterministic comparison.
package main
import (
"fmt"
"github.com/FlavioCFOliveira/GoGraph/graph/adjlist"
"github.com/FlavioCFOliveira/GoGraph/graph/csr"
"github.com/FlavioCFOliveira/GoGraph/search/centrality"
)
func main() {
// Leaves 1..5 each point at sink 0.
a := adjlist.New[int, struct{}](adjlist.Config{Directed: true})
for leaf := 1; leaf <= 5; leaf++ {
_ = a.AddEdge(leaf, 0, struct{}{})
}
c := csr.BuildFromAdjList(a)
m := a.Mapper()
ranks, _, err := centrality.PageRank(c, centrality.DefaultPageRankOptions())
if err != nil {
fmt.Println("error:", err)
return
}
sink, _ := m.Lookup(0)
leaf, _ := m.Lookup(1)
fmt.Printf("sink rank = %.4f\n", ranks[sink])
fmt.Printf("leaf rank = %.4f\n", ranks[leaf])
}
Output: sink rank = 0.5122 leaf rank = 0.0976
func PageRankCtx ¶
func PageRankCtx[W any](ctx context.Context, c *csr.CSR[W], opts PageRankOptions) (ranks []float64, iterations int, err error)
PageRankCtx is the context-aware variant of PageRank. ctx.Err() is checked at every iteration boundary; on cancellation returns (nil, 0, wrapped ctx.Err()).
This is the one-shot hot path: its computation is kept as a single monolithic function (rather than routed through the PageRanker state machinery) so the compiler keeps every working buffer in one frame — extracting it behind a method boundary measurably regressed the parallel SpMV by ~3%. PageRanker.Run carries the reusable variant for repeated queries.
func PersonalisedPushPageRank ¶
func PersonalisedPushPageRank[W any](c *csr.CSR[W], src graph.NodeID, opts PPRPushOptions) ([]float64, error)
PersonalisedPushPageRank computes the personalised PageRank vector seeded at src using the local-push algorithm (Andersen-Chung-Lang, FOCS 2006). Returns the rank vector indexed by NodeID.
The algorithm pays only for the edges it touches, so on large graphs with a small high-probability cluster it runs in roughly O(1/epsilon) time rather than O(V+E).
Dangling-node handling matches the ACL paper: residue at a node with out-degree 0 is teleported back to src (probability alpha) rather than redistributed to non-existent neighbours. This keeps the rank vector summing to 1 within numerical tolerance.
Concurrency: safe to invoke from any number of goroutines on a shared CSR.
func PersonalisedPushPageRankCtx ¶
func PersonalisedPushPageRankCtx[W any](ctx context.Context, c *csr.CSR[W], src graph.NodeID, opts PPRPushOptions) ([]float64, error)
PersonalisedPushPageRankCtx is the context-aware variant of PersonalisedPushPageRank. ctx.Err() is checked every 4096 worklist pops; on cancellation returns (nil, wrapped ctx.Err()).
func WeightedBetweenness ¶
WeightedBetweenness computes the weighted betweenness centrality of every NodeID in c using Dijkstra-augmented Brandes (Brandes 2001 §3, weighted variant). Edge weights must be finite and strictly positive.
Complexity is O(V * (E log V)) for binary-heap-backed Dijkstra per source. The result is not normalised; callers wanting the classical 1 / ((n-1)(n-2)) factor can divide externally.
Input contract. Returns ErrInvalidInput when any edge weight is NaN or +/-Inf; returns ErrNonPositiveWeight when any edge weight is zero or negative (zero-weight edges can silently corrupt path counts σ when two predecessors settle at equal distance).
Concurrency: WeightedBetweenness is safe to invoke concurrently on a shared CSR.
func WeightedBetweennessCtx ¶
WeightedBetweennessCtx is the context-aware variant of WeightedBetweenness. ctx.Err() is checked once per source vertex; on cancellation returns (nil, wrapped ctx.Err()).
func WeightedBetweennessParallel ¶ added in v0.6.0
WeightedBetweennessParallel computes the weighted betweenness centrality of every NodeID in c using Dijkstra-augmented Brandes (Brandes 2001 §3, weighted variant) parallelised across sources. Each worker goroutine processes a disjoint stripe of source vertices, accumulating into its own private centrality buffer; the final reduction sums those buffers into the returned slice in worker-id order. Edge weights must be finite and strictly positive.
Output is deterministic for a fixed numWorkers value. It is NOT numerically equal to the serial WeightedBetweenness: parallelising over sources re-associates the cross-source dependency sum, and IEEE-754 floating-point addition is non-associative, so the result may differ from WeightedBetweenness by up to ~1e-12 per node when numWorkers > 1; the two agree within this numerical tolerance. For an exact, reproducible-against-serial result use WeightedBetweenness directly.
numWorkers <= 0 picks runtime.GOMAXPROCS(0). For tiny graphs (V below ~1024) the parallel overhead dominates and the serial WeightedBetweenness is preferable.
Input contract. Returns ErrInvalidInput when any edge weight is NaN or +/-Inf; returns ErrNonPositiveWeight when any edge weight is zero or negative — identical to WeightedBetweenness.
Concurrency: WeightedBetweennessParallel reads the immutable CSR without synchronisation and is safe to invoke concurrently on a shared CSR; every worker owns its private scratch.
func WeightedBetweennessParallelCtx ¶ added in v0.6.0
func WeightedBetweennessParallelCtx(ctx context.Context, c *csr.CSR[float64], numWorkers int) ([]float64, error)
WeightedBetweennessParallelCtx is the context-aware variant of WeightedBetweennessParallel. ctx cancellation is checked once per source vertex inside every worker; on cancellation returns (nil, wrapped ctx.Err()).
Types ¶
type EigenvectorOptions ¶ added in v0.6.0
EigenvectorOptions configures Eigenvector. It is an immutable value with no shared state and is safe for concurrent use (copy it freely across goroutines).
func DefaultEigenvectorOptions ¶ added in v0.6.0
func DefaultEigenvectorOptions() EigenvectorOptions
DefaultEigenvectorOptions returns the NetworkX-compatible parameters (max 100 iterations, tolerance 1e-6).
type KatzOptions ¶ added in v0.6.0
KatzOptions configures Katz. It is an immutable value with no shared state and is safe for concurrent use (copy it freely across goroutines).
Alpha is the attenuation factor. Convergence of the Katz series requires Alpha < 1/λ_max, where λ_max is the largest eigenvalue of the adjacency matrix. When Alpha <= 0 a safe default is chosen automatically from the degree bound (λ_max ≤ d_max): Alpha = 0.85 / (1 + maxInDegree), which always satisfies the convergence condition. Supply an explicit Alpha only when you know it stays below 1/λ_max.
Beta is the per-node baseline status (default 1.0 when <= 0).
func DefaultKatzOptions ¶ added in v0.6.0
func DefaultKatzOptions() KatzOptions
DefaultKatzOptions returns parameters with auto-selected Alpha (0 sentinel), Beta 1.0, max 1000 iterations, tolerance 1e-6.
type PPRPushOptions ¶
type PPRPushOptions struct {
// Damping is the random-jump probability (alpha; typical 0.85).
Damping float64
// Epsilon stops propagation when residue/outdeg falls below it.
Epsilon float64
// MaxSteps caps the number of push operations for safety.
MaxSteps int
}
PPRPushOptions controls PersonalisedPushPageRank.
func DefaultPPRPushOptions ¶
func DefaultPPRPushOptions() PPRPushOptions
DefaultPPRPushOptions returns the Andersen-Chung-Lang reference parameters (damping 0.85, epsilon 1e-6, max 1e7 steps).
type PageRankOptions ¶
PageRankOptions configures PageRank.
func DefaultPageRankOptions ¶
func DefaultPageRankOptions() PageRankOptions
DefaultPageRankOptions returns the classic Brin-Page parameters (damping 0.85, max 100 iterations, tolerance 1e-6).
type PageRanker ¶ added in v0.6.0
type PageRanker[W any] struct { // contains filtered or unexported fields }
PageRanker is a stateful, reusable PageRank computer bound to one immutable CSR snapshot. It caches the CSR-derived working storage — the live/out-degree topology and, on the parallel path, the reverse-CSR transpose — so that repeated PageRanker.Run calls on the same snapshot skip those one-time allocations. It mirrors the stateless PageRank / stateful split used elsewhere in the package (e.g. search.Dijkstra vs search.DijkstraInto).
Use it for repeated-query workloads (parameter sweeps over Damping or MaxIterations, convergence studies, A/B comparisons) on a single graph. For a single computation, prefer the one-shot PageRank.
Concurrency ¶
A PageRanker owns mutable working buffers and is therefore NOT safe for concurrent use: a single PageRanker must not have Run invoked from more than one goroutine at a time. To run PageRank concurrently over a shared CSR, give each goroutine its own PageRanker (or call the one-shot PageRank); because the underlying CSR is immutable and read-only, independent PageRankers over the same snapshot are race-free.
Result aliasing ¶
The []float64 returned by Run aliases an internal buffer and is invalidated by the next Run call on the same PageRanker. Callers that need the rank vector to outlive the next Run must copy it.
func NewPageRanker ¶ added in v0.6.0
func NewPageRanker[W any](c *csr.CSR[W]) *PageRanker[W]
NewPageRanker builds a reusable PageRanker over the immutable snapshot c. The CSR-derived topology is built eagerly; the reverse-CSR transpose (needed only by the parallel path) is built lazily on the first Run that selects it and then cached for subsequent runs.
func (*PageRanker[W]) Run ¶ added in v0.6.0
func (p *PageRanker[W]) Run(ctx context.Context, opts PageRankOptions) (ranks []float64, iterations int, err error)
Run computes PageRank over the bound snapshot with opts and returns the per-NodeID rank slice plus the iteration count to convergence. The returned slice aliases an internal buffer (see the type's Result aliasing note) and is invalidated by the next Run.
The result is bit-for-bit identical to the equivalent one-shot PageRankCtx call: Run re-seeds the rank vectors from scratch on every invocation and consumes the same shared core, so reusing cached state changes only the allocation profile, never the output.
Source Files