graph-analytics

sparq-algos — graph analytics

sparq-algos is an opt-in crate (vendor-parity, epic sq-3183) that runs classic graph algorithms over a sparq_core::Graph: PageRank, degree centrality (in / out / total), feature-gated exact Brandes betweenness, harmonic closeness, and k-core decomposition, weakly-connected components, and a deterministic label-propagation community heuristic, plus feature-gated directed strongly connected components and boolean acyclicity checks and topological sorting. It consumes only sparq-core's public read API (the borrowing triple-id iterator + dict lookups), holds no graph state of its own, and nothing in the workspace depends on it — the default engine build does not even compile it.

These are topology algorithms: every triple (s, p, o) becomes one directed edge s → o, the predicate is erased, parallel edges are collapsed, and edges are unweighted. To analyse a single relation (e.g. only foaf:knows), filter the source graph first. There is no SPARQL-level integration — call the Rust API directly.

Quickstart

crates/sparq-algos/Cargo.toml (optional algorithm groups are explicitly enabled here):

[dependencies]
sparq-core  = { path = "../sparq-core" }
sparq-algos = { path = "../sparq-algos", features = ["centrality-extended", "topology"] }
oxrdf = "*"   # for oxrdf::{NamedNode, Term} when resolving node indices back to terms

Build the view once, then run any algorithm over it:

use sparq_algos::{
    NodeGraph, NodeFilter,
    pagerank, PageRankConfig,
    degree_centrality, degree_centrality_normalized, Direction, top_k,
    betweenness_centrality, closeness_centrality, core_number,
    weakly_connected_components, label_propagation, LabelPropConfig, num_communities,
    is_acyclic, num_strongly_connected_components, strongly_connected_components,
    topological_sort,
};

// Project the RDF graph onto a directed node graph.
let g = NodeGraph::build(&graph);                          // entities only (literals dropped)
let g = NodeGraph::build_with(&graph, NodeFilter::All);    // include literal objects as nodes

// --- PageRank: stationary distribution, sums to ~1.0, indexed by node index ---
let ranks = pagerank(&g, PageRankConfig::default());       // d = 0.85, tol 1e-9
// node index -> the original RDF term:
let top_node = (0..g.len()).max_by(|&a, &b| ranks[a].total_cmp(&ranks[b])).unwrap();
let term = g.term(&graph, top_node);                       // oxrdf::Term

// --- Degree centrality (raw counts or normalised), plus the top-k ---
let indeg = degree_centrality(&g, Direction::In);          // Vec<usize>, per node
let norm  = degree_centrality_normalized(&g, Direction::Total); // Vec<f64> in [0,1]
let top10 = top_k(&indeg, 10);                             // Vec<(node_index, score)>, best first

// --- Exact shortest-path centrality over the weak (undirected) topology ---
let between = betweenness_centrality(&g);                  // unnormalised; unordered pairs
let close   = closeness_centrality(&g);                    // normalised harmonic mean, [0, 1]
let cores   = core_number(&g);                             // largest k-core containing each node

// --- Community detection ---
let comp = weakly_connected_components(&g);                // exact, union-find; Vec<usize> labels
let comm = label_propagation(&g, LabelPropConfig::default()); // deterministic heuristic
let k    = num_communities(&comm);                         // distinct community count

// --- Directed topology ---
let scc   = strongly_connected_components(&g);             // dense component id per node
let scc_k = num_strongly_connected_components(&scc);       // number of components
let dag   = is_acyclic(&g);                                 // false for any directed cycle
let order = topological_sort(&g)?;                         // canonical DAG order; Err on cycle