Betweenness centrality by Brandes' algorithm

Formula: c_B(v) = sum_{s != v != t} sigma_st(v) / sigma_st, accumulated by dependency delta_s(v) = sum_w (sigma_sv/sigma_sw)(1 + delta_s(w))

Usage

Btwcent(A, normalise = FALSE)

Arguments

A

See Usage.

normalise

When TRUE, betweenness is divided by (n - 1)(n - 2) / 2; the raw counts stay in raw.

Value

List with betweenness, normalised, n.

References

Brandes (2001), A faster algorithm for betweenness centrality, Journal of Mathematical Sociology 25:163-177. Paywalled and The dependency recursion implemented here is the standard published form of the algorithm. Its output is checked in the batch's anchor file against brute-force enumeration of all shortest paths on a small graph.

Examples

V <- c(1, 2, 3, 4, 5, 6, 7, 8)
Btwcent(V)
#> $betweenness
#> [1] 0 0 0 0 0 0 0 0
#> 
#> $raw
#> [1] 0 0 0 0 0 0 0 0
#> 
#> $normalised
#> [1] 0 0 0 0 0 0 0 0
#> 
#> $n
#> [1] 8
#> 
#> $method
#> [1] "Betweenness centrality (Brandes)"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"