12. betweenness - the bridges in a network

what this does

betweenness scores each node by how many shortest paths run through it - the centrality that finds bridges and brokers rather than merely popular nodes. GET /v1/tenants/:t/graph/:schema/betweenness returns one row per node, sorted by score descending. It is exact by default, and exact betweenness is expensive, so the endpoint refuses on predicted work rather than letting a large graph run past its request budget.

when to use it

• Finding the nodes whose removal would split the network. This is the single most useful centrality for resilience and for fraud work.
• Ranking brokers - accounts, services or documents that sit between clusters rather than inside one.
• Prioritising review. A bridge with a small degree is much more interesting than a hub with a large one, and only betweenness tells them apart.

schema requirement

The relation must be declared in the schema's [[relations]] block and must target the table it is declared on. See schemas/reference#relations.

the request

rel is required. max_nodes caps the node universe and defaults to the engine's 100,000-node ceiling. samples=K switches to the Brandes-Pich estimate over K random pivots and seed fixes which pivots get chosen. Exact is the default and is never substituted automatically: an approximation you did not ask for and cannot detect would be a correctness bug, so the sampled mode has to be requested explicitly.

curl -G "https://$OC_HOST/v1/tenants/$OC_TENANT/graph/social.users/betweenness" \
  --data-urlencode "rel=follows" \
  -H "Authorization: Bearer $OC_TOKEN"

scores = db.graph.betweenness("social.users", rel="follows")
# The wire `pk` is an array, so the SDK keys the dict by its JSON
# encoding: {'["dave"]': 8.0, '["carol"]': 5.0, ...}
#
# The SDK exposes rel and max_nodes only. Call the endpoint
# directly when you need samples= or seed=.

// The TypeScript SDK does not wrap the graph algorithms - use fetch.
const qs = new URLSearchParams({ rel: "follows" });
const res = await fetch(
  `https://${OC_HOST}/v1/tenants/${OC_TENANT}/graph/social.users/betweenness?${qs}`,
  { headers: { Authorization: `Bearer ${OC_TOKEN}` } },
);
const ranked = await res.json();

// The Go SDK does not wrap the graph algorithms - use net/http.
url := "https://" + OC_HOST + "/v1/tenants/" + OC_TENANT +
    "/graph/social.users/betweenness?rel=follows"

req, _ := http.NewRequestWithContext(ctx, "GET", url, nil)
req.Header.Set("Authorization", "Bearer "+OC_TOKEN)

resp, _ := http.DefaultClient.Do(req)
defer resp.Body.Close()

var ranked []struct {
    PK          []string `json:"pk"`
    Betweenness float64  `json:"betweenness"`
    Estimated   bool     `json:"estimated"`
    Pivots      int      `json:"pivots"`
}
json.NewDecoder(resp.Body).Decode(&ranked)

what you get back

[
  { "pk": ["dave"],    "betweenness": 8.0 },
  { "pk": ["carol"],   "betweenness": 5.0 },
  { "pk": ["bob"],     "betweenness": 1.0 },
  { "pk": ["alice"],   "betweenness": 0.0 },
  { "pk": ["mallory"], "betweenness": 0.0 }
]

[
  { "pk": ["dave"],  "betweenness": 7.6, "estimated": true, "pivots": 500 },
  { "pk": ["carol"], "betweenness": 4.8, "estimated": true, "pivots": 500 }
]

One row per node, sorted by score descending, with pk as the primary-key array. In exact mode - the first body above - each row has exactly two fields: there is no estimated and no pivots key at all, so a parser written against the exact shape keeps working. Add samples=K and you get the second body: every row is tagged estimated: true with the pivot count, which is what lets a consumer holding only the response tell that it is looking at an approximation.

how it works

• Brandes' algorithm runs a single-source shortest-path pass from every node and accumulates dependency scores on the way back.
• Cost grows with nodes times edges, so this endpoint refuses on predicted work, not on node count. The refusal is a tagged graph_work_budget_exceeded 400 that quotes the node and edge counts, the predicted seconds, and the samples= value that would fit - it tells you what to do instead of timing out.
• Sampled mode runs the same pass from K randomly chosen pivots instead of from every node, which is what makes a large graph fit inside a request.
• seed fixes pivot selection and has a fixed default, so a sampled result is reproducible even when you do not pass one.
• Sampling only helps where the graph has a distinguishable head. Take the ratio of the top score to the median over the rows you get back: where that ratio is large the sampled ranking tracks the exact one closely, and where it is close to one every node has nearly the same betweenness and no ranking of that graph means much - including the exact one.