Betweenness and harmonic closeness centrality, from one walk.
Betweenness is the share of shortest paths between other nodes that pass
through a node -- how much of a bridge or a broker it is. Brandes' algorithm
over unweighted edges, normalised to 0..1 by the number of ordered pairs of
other nodes, (n − 1)(n − 2), so a value reads the same on a graph of any
size. On an undirected graph every path is found from both of its ends,
which that divisor already accounts for: the centre of a star scores 1
either way. A pair with no path between them adds nothing, so a graph in
several pieces is measured within each piece.
Harmonic closeness is how near a node is to all the others: the mean of
1 / distance over every other node. The harmonic form rather than the
reciprocal of summed distances, because these graphs are often in several
pieces, and an unreachable node then adds zero instead of making every
distance infinite. A node linked directly to every other scores 1, an
isolated node 0. On a directed graph it measures how near the nodes a node
reaches are.
Each walk's credit flows back along the edges it came down, read from the
distances rather than from a list of predecessors kept per node, so the walk
reuses the same few typed arrays for every source.
Parameters
adjacency: readonly (readonlynumber[])[]
Each node's neighbours. For an undirected graph, list every
edge from both ends
Betweenness and harmonic closeness centrality, from one walk.
Betweenness is the share of shortest paths between other nodes that pass through a node -- how much of a bridge or a broker it is. Brandes' algorithm over unweighted edges, normalised to 0..1 by the number of ordered pairs of other nodes,
(n − 1)(n − 2), so a value reads the same on a graph of any size. On an undirected graph every path is found from both of its ends, which that divisor already accounts for: the centre of a star scores 1 either way. A pair with no path between them adds nothing, so a graph in several pieces is measured within each piece.Harmonic closeness is how near a node is to all the others: the mean of
1 / distanceover every other node. The harmonic form rather than the reciprocal of summed distances, because these graphs are often in several pieces, and an unreachable node then adds zero instead of making every distance infinite. A node linked directly to every other scores 1, an isolated node 0. On a directed graph it measures how near the nodes a node reaches are.Each walk's credit flows back along the edges it came down, read from the distances rather than from a list of predecessors kept per node, so the walk reuses the same few typed arrays for every source.