tbc {TNC}

Temporal betweenness centrality

Description

tbc returns the temporal betweenness centrality for each node in a dynamic network (sequence of graph snapshots).

Usage

tbc(x, type = NULL, startsnapshot = 1, endsnapshot = length(x),
  vertexindices = NULL, directed = FALSE, normalize = TRUE,
  centrality_evolution = FALSE)

Arguments

x

A list of adjacency matrices or a list of adjacency lists.

type

Data format of x. Possible formats are "M" for a list of adjacency matrices (containing only 1s and 0s) and "L" for a list of adjacency lists (adjacency lists of the igraph package are supported). Default is NULL.

startsnapshot

Numeric. Entry of x to start the calculation of tbc. Default is 1.

endsnapshot

Numeric. Entry of x to end the calculation of tbc. Default is the last element of x.

vertexindices

Numeric. A vector of nodes. Only shortest temporal paths ending at nodes in vertexindices are considered for calculating tbc. Can be used to parallel the calculation of tbc (see section Examples). Default is NULL.

directed

Logical. Set TRUE if the dynamic network is a directed network. Default is FALSE.

normalize

Logical. Set TRUE if centrality values should be normalized with 1/((|V|-1)*(|V|-2)*m) where |V| is the number of nodes and m = endsnapshot - startsnapshot. Default is TRUE.

centrality_evolution

Logical. Set TRUE if an additional matrix should be returned containing the centrality values at each snapshot. Rows correspondent to nodes, columns correspondent to snapshots. Default is FALSE.

Details

tbc calculates the temporal betweenness centrality (Kim and Anderson, 2012). To keep the computational effort linear in the number of snapshots the Reversed Evolution Network algorithm (REN; Hanke and Foraita, 2017) is used to find all shortest temporal paths.

Value

The (normalized) temporal betweenness centrality (TBC) values of all nodes. If centrality_evolution is TRUE, an additional matrix will be returned (CentEvo), containing the temporal (|V| x T) matrix is returned (CentEvo), containing the temporal centrality value at each snapshot between startsnapshot and endsnapshot.

Warning

Using adjacency matrices as input exponentially increases the required memory. Use adjacency lists to save memory.

References

Kim, Hyoungshick and Anderson, Ross (2012). Temporal node centrality in complex networks. Physical Review E, 85 (2).

Hanke, Moritz and Foraita, Ronja (2017). Clone temporal centrality measures for incomplete sequences of graph snapshots. BMC Bioinformatics, 18 (1).

See Also

tcc,tdc

Examples

# Create a list of adjacency matrices, plot the corresponding graphs
# (using the igraph package) and calculate tbc

A1 <- matrix(c(0,1,0,0,0,0,
               1,0,1,0,0,0,
               0,1,0,0,0,0,
               0,0,0,0,0,0,
               0,0,0,0,0,0,
               0,0,0,0,0,0), ncol=6)

A2 <- matrix(c(0,0,0,0,0,0,
               0,0,1,0,0,0,
               0,1,0,1,1,0,
               0,0,1,0,0,0,
               0,0,1,0,0,0,
               0,0,0,0,0,0), ncol=6)

A3 <- matrix(c(0,0,0,0,0,0,
               0,0,0,0,0,0,
               0,0,0,0,0,0,
               0,0,0,0,0,0,
               0,0,0,0,0,0,
               0,0,0,0,0,0), ncol=6)

A4 <- matrix(c(0,1,0,0,0,0,
               1,0,0,1,0,0,
               0,0,0,0,0,0,
               0,1,0,0,0,0,
               0,0,0,0,0,0,
               0,0,0,0,0,0), ncol=6)

library(igraph)
par(mfrow=c(2,2))

Layout <-
 layout_in_circle(graph_from_adjacency_matrix(A1, mode = "undirected"))

plot(graph_from_adjacency_matrix(A1, "undirected"), layout=Layout)
plot(graph_from_adjacency_matrix(A2, "undirected"), layout=Layout)
plot(graph_from_adjacency_matrix(A3, "undirected"), layout=Layout)
plot(graph_from_adjacency_matrix(A4, "undirected"), layout=Layout)

As <- list(A1,A2,A3,A4)

tbc(As, "M", centrality_evolution=TRUE)

### Create list of adjacency lists
Ls <- lapply(seq_along(As), function(i){
  sapply(1:6, function(j){which(As[[i]][j,]==1)})
})

tbc(Ls, "L", centrality_evolution=TRUE)

### Run tbc in parallel ###
library(parallel)
# Calculate the number of cores
cores_avail <- detectCores()-1
# Initiate cluster
cl <- makeCluster(2)
clusterExport(cl, c("As", "tbc"))

TBC <- parLapply(cl, 1:6, function(x){
  tbc(As, "M", vertexindices = x)
 }
)

stopCluster(cl)

Reduce("+", TBC)