algorithm

func AllShortestPathLength ¶

func AllShortestPathLength(g *graph.Graph, cfg *config.Config) path.PathLength

AllShortestPathLength returns all-pairs unweighted shortest path lengths. - For each source u, the inner map contains v -> dist(u,v) for all reachable v (including u with 0). - Unreachable targets are omitted from the inner map. - Uses a worker pool sized by cfg.Workers (or NumCPU when <=0).

func AllShortestPaths ¶

func AllShortestPaths(g *graph.Graph, cfg *config.Config) path.GraphPaths

AllShortestPaths computes all-pairs shortest paths while keeping the same return structure (path.GraphPaths). Performance improvements over the (s,t)-pair BFS approach:

• Run exactly one BFS per source node (O(n*(m+n)) instead of O(n^2*(m+n)) in the worst case).
• Reconstruct all shortest paths to every target using predecessors (no repeated BFS).
• Use memoization to enumerate all s->u shortest paths once and reuse for all targets.

Notes:

• For undirected graphs we fill symmetric entries [t][s] with the SAME slice reference as [s][t] (matching prior behavior and saving work). If you need reversed node order per entry, that can be changed, but be aware of the extra cost.
• Self paths [u][u] are set to a single self path.

func BetweennessCentrality ¶

func BetweennessCentrality(g *graph.Graph, cfg *config.Config) map[node.ID]float64

BetweennessCentrality computes betweenness centrality using cached all shortest paths. - Uses AllShortestPaths(g, cfg) (assumed cached/fast) to enumerate all shortest paths. - For each pair (s,t), each interior node on a shortest path gets 1/|SP(s,t)| credit. - Undirected graphs enqueue only i<j pairs (no double counting). - Normalization matches NetworkX: undirected => 2/((n-1)(n-2)), directed => 1/((n-1)(n-2)).

func CacheClear ¶ added in v0.6.1

func CacheClear()

CacheClear clears the cached shortest paths and their lengths.

func ClosenessCentrality ¶

func ClosenessCentrality(g *graph.Graph, cfg *config.Config) map[node.ID]float64

ClosenessCentrality computes NetworkX-compatible closeness centrality.

Semantics:

• Directed + Reverse=false => OUT-closeness on G (matches nx.closeness_centrality(G))
• Directed + Reverse=true => IN-closeness on G (matches nx.closeness_centrality(G.reverse()))
• Undirected => standard closeness.

Distances are unweighted (#edges) and come from cached all-pairs shortest paths.

Requirements: - AllShortestPaths(g, cfg) must respect directedness of g. - cfg.Closeness.WfImproved follows NetworkX default (true) unless overridden.

func ClusteringCoefficient ¶

func ClusteringCoefficient(g *graph.Graph, cfg *config.Config) map[node.ID]float64

ClusteringCoefficientAll computes local clustering coefficients for all nodes. - If g.IsBidirectional()==false (directed): Fagiolo (2007) directed clustering (matches NetworkX). - If g.IsBidirectional()==true (undirected): standard undirected clustering. Returns map[node.ID]float64 with a value for every node in g.

func DegreeAssortativityCoefficient ¶ added in v0.6.4

func DegreeAssortativityCoefficient(g *graph.Graph, cfg *config.Config) float64

DegreeAssortativityCoefficient computes Newman's degree assortativity coefficient (Pearson correlation) between degrees at the two ends of each edge/arc, with behavior controlled by cfg.Assortativity.

Assumptions / Notes: - For undirected graphs, it counts each edge once using upper-triangle filtering by node index. - For directed graphs:

• Mode "projected": ignores direction and uses undirected degrees on both ends.
• Mode "out-in": j = out(u), k = in(v) over arcs u->v
• Mode "out-out": j = out(u), k = out(v)
• Mode "in-in": j = in(u), k = in(v)
• Mode "in-out": j = in(u), k = out(v)

- Self-loops are ignored by default (configurable). - Replace neighbor getters with your Graph's actual API if different.

func DegreeCentrality ¶

func DegreeCentrality(g *graph.Graph, cfg *config.Config) map[node.ID]float64

DegreeCentrality computes degree-based centrality with NetworkX-compatible semantics. - Undirected: deg(u)/(n-1). - Directed (default "total"): (in(u)+out(u))/(n-1). Use "in"/"out" for the specific variants. Self-loops are ignored for centrality.

func Diameter ¶

func Diameter(g *graph.Graph, cfg *config.Config) int

Diameter computes the diameter of the graph using all-pairs shortest paths.

func EdgeBetweennessCentrality ¶

func EdgeBetweennessCentrality(g *graph.Graph, cfg *config.Config) map[node.ID]map[node.ID]float64

EdgeBetweennessCentrality computes edge betweenness centrality (unweighted) compatible with NetworkX's nx.edge_betweenness_centrality.

Algorithm:

• Brandes (2001) single-source shortest paths with dependency accumulation, extended for edges.

Parallelization:

• Sources (s) are split across a worker pool (cfg.Workers).

Normalization (normalized=true):

• Directed: multiply by 1 / ((n-1)*(n-2))
• Undirected: multiply by 2 / ((n-1)*(n-2))

Additionally, undirected results are divided by 2 to correct for double counting in Brandes accumulation (same practice as NetworkX).

Returns:

• map[node.ID]map[node.ID]float64 where:
• Undirected: key is canonical [min(u,v), max(u,v)]
• Directed: key is (u,v) ordered

func EigenvectorCentrality ¶

func EigenvectorCentrality(g *graph.Graph, cfg *config.Config) map[node.ID]float64

EigenvectorCentrality computes eigenvector centrality using parallel power iteration. Semantics match NetworkX by default:

• Undirected graphs: neighbors are used (symmetric).
• Directed graphs: by default (Reverse=false) we use predecessors/in-edges (left eigenvector). Set Reverse=true to use successors/out-edges (right eigenvector).

Unweighted edges are assumed. The result vector is L2-normalized (sum of squares == 1).

func GreedyModularityCommunitiesNX ¶ added in v0.6.4

func GreedyModularityCommunitiesNX(g *graph.Graph) map[node.ID]int

GreedyModularityCommunitiesNX implements the Clauset–Newman–Moore greedy modularity maximization, aligned with NetworkX conventions: - work on an undirected projection - m = number_of_undirected_edges - inv2m = 1/(2m); each undirected edge contributes inv2m twice (symmetrically) Returns a partition map: nodeID -> compact community label.

func Modularity ¶ added in v0.6.4

func Modularity(g *graph.Graph, cfg *config.Config) float64

Modularity computes Newman-Girvan modularity Q. If cfg.Modularity.Partition == nil, it runs greedy CNM to obtain a partition first. All computations are performed on an undirected projection (to match NetworkX).

func PageRank ¶

func PageRank(g *graph.Graph, cfg *config.Config) map[node.ID]float64

PageRank computes PageRank using a parallel power-iteration that mirrors NetworkX semantics:

• Teleport and dangling redistribution match NetworkX (personalization used for both by default).
• Convergence check uses L1 error before any per-iteration normalization: sum(|x - x_last|) < n*tol.
• Result is L1-normalized once after convergence (or after max-iter).
• For directed graphs, Reverse=false is the standard PageRank (incoming influence). Reverse=true flips direction (treat in-neighbors as outs).
• For undirected graphs, neighbors are used as outs (degree-based normalization).

func ShortestPaths ¶

func ShortestPaths(g *graph.Graph, start, end node.ID) []path.Path

ShortestPaths finds all shortest paths between two nodes in a graph.