R/centrality-batch47.R

In cograph: Analysis and Visualization of Complex Networks

#' Simple randomized shortest paths betweenness (Kivimaki et al. 2016)
#' @keywords internal
#' @noRd
calculate_rsp_betweenness <- function(cg, weights = NULL, rsp_beta = 0.01,
                                      rsp_cost = "inverse") {
  .cg_rsp_terms(.cg_path_matrix(cg, weights), rsp_beta, rsp_cost)$score
}

#' Randomized Shortest Paths Betweenness Centrality
#'
#' Kivimaki, Lebichot, Saramaki and Saerens interpolate between shortest-path
#' betweenness and a random-walk quantity with a single knob. They place a
#' Boltzmann distribution over the absorbing walks from \eqn{s} to \eqn{t},
#' tilted by an inverse temperature \eqn{\beta} away from the unbiased random
#' walk and towards low-cost walks, and score a node by the expected number of
#' visits it receives summed over every ordered source-target pair:
#' \eqn{bet_i=\sum_{s,t}(z_{si}/z_{st}-z_{ti}/z_{tt})z_{it}}, where
#' \eqn{Z=(I-W)^{-1}} is the fundamental matrix of the killed random walk
#' \eqn{W=(D^{-1}A)\circ\exp(-\beta C)}. Large \code{rsp_beta} concentrates
#' the distribution on shortest paths; \code{rsp_beta} towards zero relaxes it
#' to the plain random walk, where the source states the score becomes
#' proportional to degree on an undirected graph.
#'
#' \strong{The published closed form is only defined on a strongly connected
#' graph, and the source says what to do otherwise.} Equation (15) divides by
#' every entry of \eqn{Z}, and Algorithm 1 takes "a directed strongly connected
#' graph" as its input, but the text below equation (9) settles the general
#' case directly: the derivation "holds only if there exists a path from
#' \eqn{s} to \eqn{t}. Otherwise, naturally, \eqn{\bar\eta_{ij}(s,t)=0}."
#' cograph applies that zero rule to the whole term of an unreachable pair and
#' evaluates the closed form masked by reachability, which reproduces equation
#' (15) to machine precision whenever the graph is strongly connected and
#' extends it consistently when it is not. The mask has to reach \emph{both}
#' halves of the term, since both come from the same
#' \eqn{\bar n_i(s,t)}; \code{NetworkToolbox::rspbc()} masks only the
#' reciprocal and leaves the \eqn{n\,\mathrm{Diag}(Z^{\div})} half counting
#' every source, so the two part company on a disconnected graph and agree
#' exactly on a strongly connected one.
#'
#' \strong{The consequence is that scores are component-local.} A node's score
#' depends only on the pairs it can stand between, so two disjoint triangles
#' score exactly what one triangle scores, and adding a disconnected component
#' -- an isolate included -- leaves every existing score untouched. That is a
#' cograph decision, taken because the source resolves the unreachable pair
#' rather than because the source discusses disconnected graphs, which it does
#' not.
#'
#' \strong{Zero out-degree is a derived zero, not an imputed one.}
#' \eqn{D^{-1}} is undefined at out-degree zero. cograph writes that row of
#' \eqn{P^{ref}} as zero, which is the paper's own killed random walk read at a
#' node where the walker dies at once; \eqn{Z} then has \eqn{z_{ii}=1} and the
#' arithmetic gives exactly \eqn{1-1=0}. An isolate, a singleton graph and
#' every node of an edgeless graph therefore score zero because the formula
#' says so. \code{NetworkToolbox::rspbc()} raises an error on such input, and
#' \code{\link{centrality_current_flow_betweenness}} returns \code{NA} on
#' disconnected input; this measure is able to answer where those cannot,
#' because \eqn{(I-W)} stays nonsingular whatever the connectivity.
#'
#' \strong{\code{rsp_beta} defaults to 0.01, which is not the source's
#' number.} The paper fixes no default and treats \eqn{\beta} as a modeling
#' choice; 0.01 is the value recommended by \code{NetworkToolbox::rspbc()},
#' adopted here so that the two implementations are directly comparable out of
#' the box. It sits near the high-temperature end, so the default reading is
#' close to the random-walk limit and far from shortest-path betweenness --
#' raise it, to 1 or beyond, to move towards shortest paths. The domain is
#' \eqn{\beta>0}; zero and negative values are refused with a
#' \code{cograph_bad_parameter} error rather than extended, since
#' \eqn{\beta\le 0} is outside the Boltzmann model and can make \eqn{W} leave
#' the substochastic regime the inverse depends on.
#'
#' \strong{\code{rsp_cost} chooses how a weight becomes a cost, because the
#' source leaves \eqn{C} free.} Algorithm 1 takes the cost matrix as an input
#' and never derives it from the weights. \code{"inverse"}, the default, sets
#' \eqn{C=1/w}, reading a weight as an affinity so a heavier edge is cheaper;
#' this is cograph's usual convention for a weight and the one
#' \code{NetworkToolbox::rspbc()} hard-codes. \code{"weight"} sets \eqn{C=w},
#' reading a weight as a distance. The two coincide on a binary graph, where
#' both give unit cost per arc, so the choice only bites on genuinely weighted
#' input. Negative or non-finite weights are refused with a
#' \code{cograph_bad_input} error: Algorithm 1 requires a non-negative cost
#' matrix, and a negative cost makes \eqn{\exp(-\beta C)>1} and the Neumann
#' series diverge.
#'
#' Direction is read from the graph, not from \code{mode}: \eqn{P^{ref}}
#' normalizes by out-strength and \eqn{Z} counts directed walks, so a directed
#' input is scored as directed and a reversed input generally scores
#' differently. There is no in/out/all variant to select, so the measure sits
#' in the no-mode family. Loops are dropped and \code{cutoff} and
#' \code{invert_weights} are ignored; the source discusses none of the three.
#' The source states no normalization, so \code{normalized = TRUE} max-scales
#' the finished vector as elsewhere in \code{\link{centrality}}.
#'
#' Marked \strong{costly}: one dense \eqn{n\times n} inverse, which the source
#' itself calls the computational bottleneck at \eqn{O(n^3)} time and
#' \eqn{O(n^2)} memory, "because of which the method is currently not
#' practical with very large networks" (page 7). It is held back from
#' \code{centrality(type = "all")} and computed whenever named directly.
#'
#' Numerical verification establishes agreement with the definition and with
#' \code{NetworkToolbox::rspbc()} on strongly connected input after undoing
#' that function's rounding and shifting, which are its own post-processing
#' and are nowhere in the paper. The paper prints no table of node scores on a
#' small graph, so there is no published per-node example to reproduce; what
#' is checked against the paper instead is the printed limit claim on page 9,
#' that the score becomes proportional to degree as \eqn{\beta\to 0^+} on an
#' undirected graph.
#'
#' @param x Network input accepted by \code{\link{centrality}}.
#' @param ... Additional arguments to \code{\link{centrality}}, including
#'   \code{rsp_beta} and \code{rsp_cost}.
#' @return Named numeric vector in input node order.
#' @references
#' Kivimaki, I., Lebichot, B., Saramaki, J. and Saerens, M. (2016). Two
#'   betweenness centrality measures based on Randomized Shortest Paths.
#'   Scientific Reports, 6, 19668. \doi{10.1038/srep19668}.
#' @seealso \code{\link{centrality_current_flow_betweenness}} and
#'   \code{\link{centrality_random_walk}} for the random-walk end of the same
#'   spectrum, \code{\link{centrality_betweenness}} for the shortest-path end,
#'   and \code{\link{list_centralities}} for the catalogue.
#' @export
#' @examplesIf requireNamespace("igraph", quietly = TRUE)
#' # A single edge scores exactly 1 at both nodes, for every rsp_beta.
#' centrality_rsp_betweenness(igraph::make_full_graph(2))
#'
#' # A directed cycle scores n (n - 1) / 2 everywhere, independently of
#' # rsp_beta: every ordered pair is joined by exactly one directed path.
#' centrality_rsp_betweenness(igraph::make_ring(5, directed = TRUE))
#'
#' # Raising rsp_beta moves the reading from the random walk towards
#' # shortest paths, and can reorder the nodes.
#' kite <- igraph::make_graph(c(1,2, 1,3, 1,4, 1,6, 2,4, 2,5, 2,7, 3,4, 3,6,
#'                              4,5, 4,6, 4,7, 5,7, 6,7, 6,8, 7,8, 8,9, 9,10),
#'                            directed = FALSE)
#' centrality_rsp_betweenness(kite)
#' centrality_rsp_betweenness(kite, rsp_beta = 1)
centrality_rsp_betweenness <- function(x, ...) {
  df <- centrality(x, measures = "rsp_betweenness", ...)
  stats::setNames(df$rsp_betweenness, df$node)
}