Module betweenness 

How often each node sits in the middle of somebody else’s shortest path.

Brandes, “A faster algorithm for betweenness centrality”, Journal of Mathematical Sociology 2001, sampled the way Brandes and Pich describe in “Centrality estimation in large networks”, Int. J. Bifurcation and Chaos 2007.

What it measures, and why it is not PageRank

super::pagerank() says a node is important if important nodes point at it. Betweenness says a node is important if traffic has to go through it. The two disagree in exactly the interesting place: the one badly connected node joining two otherwise separate halves of a network has almost no PageRank and the highest betweenness in the graph. That is the node whose failure splits the network, the account brokering between two communities, the router everything crosses.

How Brandes made it affordable

Written out of the definition it is a sum over every pair of nodes, which means counting shortest paths between all of them and is cubic. Brandes’ observation is that the whole sum can be accumulated one source at a time in the time of a single search: run a breadth first search from s counting how many shortest paths reach each node, then walk the search back out from the furthest node inwards accumulating what each node owes its predecessors. That turns the problem into one search per source, and nothing else.

It is still one search per source, which on a graph with ten million nodes is ten million searches. Hence the sampling.

Why sampling is honest here

Each source contributes its own independent share of the total, so running the accumulation from a random sample of sources and scaling by how much of the graph was sampled is an unbiased estimate of the real thing. Brandes and Pich also make the point that the sources have to be picked uniformly at random: sampling the highest degree nodes, which sounds smarter, is biased and can be much worse than sampling at random.

The sources are drawn from yo_common::Rng on a fixed seed, so the estimate is an estimate but it is the same estimate every time.

Which way the edges point

A shortest path follows edges the way they point, the same as super::bfs() and super::sssp(). A caller who wants the undirected reading should say so in the graph by linking both ways.

use yo_graph::{Graph, NO_PROPS, Snapshot, algo};

let mut g = Graph::new();
// Two triangles that can only reach each other through node 3.
for (a, b) in [(1u64, 2u64), (2, 1), (2, 3), (3, 2), (3, 4), (4, 3), (4, 5), (5, 4)] {
    g.link(a, b, 1, NO_PROPS)?;
}

let s = Snapshot::of(&g);
let c = algo::betweenness(&s);
// Node 3 is on the path between both halves and nothing else is.
assert_eq!(c.top(1)[0].0, s.dense(3).unwrap());

Structs

Between

How central each node is, and how it was worked out.

Constants

PIVOTS

How many sources betweenness runs from.

Functions

betweenness

An estimate of every node’s betweenness, from PIVOTS random sources.

betweenness_exact

Every node’s betweenness, from every source, which is the real answer.

betweenness_with

The same, from a sample of the size asked for.