`R/centralities.R`

`betweenness_ctx.Rd`

Using this function allows obtaining betweenness centrality under dynamic contextual constraints. Enforcement of constraints is the task of the given user-defined function.

betweenness_ctx(g, betw_decision_fct)

g | The graph object |
---|---|

betw_decision_fct | A function enforcing constraints. The signature of the function is ``(vertex index, vertex index, vertex index) -> Bool``. |

A list of betweenness values one for each node of the graph.

The function enforcing contextual constraints is evaluated at each node during shortest path traversal. The function needs to evaluate to True or False allowing an edge to be visited or not. As parameters, the current state of the betweenness calculation is passed to the function, i.e. the starting node for which a centrality value is being calculated, the current node, and the descending node in question. If the function returns False, the descending node is not being visited.

The three nodes are passed as indices allowing for access of (external) attribute and other associated information.

Note that the decision function is evaluated more than once during path traversal. That means, there should not happen any resource-intense computation inside this function. Also, it does not allow to keep track of the status of calculation, e.g. by calculating the visited edges or something similar.

If the decision function simply returns True all the time, this function results in the unaltered betweenness centrality values.

Obtaining betweenness centrality is based on Brandes' efficient algorithm. At the current stage, the implementation allows for single-core execution only.

library(RUnit) suppressMessages(library(igraph)) suppressMessages(library(nctx)) file <- system.file("extdata", "bcde.directed.graphml", package="nctx") g_i <- read_graph(file, "graphml") betw <- igraph::betweenness(g_i) g <- copy_from_igraph(g_i) checker <- function(start, cur, nxt){ TRUE } betw_unaltered <- betweenness_ctx(g,checker) checkEquals(betw_unaltered, as.numeric(betw))#> [1] TRUElibrary(RUnit) suppressMessages(library(igraph)) suppressMessages(library(nctx)) suppressMessages(library(stringr)) file <- system.file("extdata", "bcde.ctx.dir.graphml", package="nctx") g_i <- read_graph(file, "graphml") betw <- as.numeric(igraph::betweenness(g_i, directed = igraph::is_directed(g_i))) g <- copy_from_igraph(g_i) ctx <- vertex_attr(g_i)$context ctx <- matrix(as.numeric(str_split(ctx, ";", simplify = TRUE)), nrow = length(ctx)) ctx <- ctx[,-ncol(ctx)] use_ctx <- all(dim(ctx) > 0) ctx_dim <- 2 search_max <- c() checker <- function(start, cur, nxt){ if(use_ctx){ s <- ctx[start,ctx_dim] n <- ctx[nxt,ctx_dim] v <- (n-s)/s search_max <<- c(search_max,v) } TRUE } betw_unaltered <- betweenness_ctx(g,checker) checkEquals(betw_unaltered, betw)#> [1] TRUEif(use_ctx){ search_max <- unique(sort(search_max)) checker <- function(start, cur, nxt){ s <- ctx[start,ctx_dim] n <- ctx[nxt,ctx_dim] v <- (n-s)/s v <= search_max[length(search_max)] } betw_ctx <- betweenness_ctx(g,checker) checkEquals(betw_ctx, betw) for (i in (length(search_max)-1):1){ checker <- function(start, cur, nxt){ s <- ctx[start,ctx_dim] n <- ctx[nxt,ctx_dim] v <- (n-s)/s v <= search_max[i] } betw_ctx <- betweenness_ctx(g,checker) checkTrue(all(betw_ctx <= betw)) if(all(betw_ctx == 0)) break } }