centrality

func Betweenness ¶

func Betweenness[W any](c *csr.CSR[W]) []float64

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)/2 (undirected) or (n-1)(n-2) (directed) for the classical normalised score.

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 ¶

func BetweennessCtx[W any](ctx context.Context, c *csr.CSR[W]) ([]float64, error)

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 ¶

func BetweennessParallel[W any](c *csr.CSR[W], numWorkers int) []float64

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 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.

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()).

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 ¶

func WeightedBetweenness(c *csr.CSR[float64]) ([]float64, error)

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 ¶

func WeightedBetweennessCtx(ctx context.Context, c *csr.CSR[float64]) ([]float64, error)

WeightedBetweennessCtx is the context-aware variant of WeightedBetweenness. ctx.Err() is checked once per source vertex; on cancellation returns (nil, wrapped ctx.Err()).