How to get the sum of edge weight from a node to a node from a graph

Viewed 652

We can sum up the edge weights of the adjacent edges for each vertex using the strength function of the igraph package. Say we have a graph like the below one

graph

Reproducible Data and Code

nodeA <- c("ID_1", "ID_2", "ID_3", "ID_4", "ID_5", "ID_16", "Node_30")
nodeB <- c("ID_11", "ID_3", "ID_4", "ID_5", "ID_3", "ID_11", "Node_3")
edge_weight <- c(0.5, 0.9, 0.8, 0.7, 0.5, 0.09, 0.7)
df_1 <- data.frame(nodeA, nodeB, edge_weight)

graph1 <- graph_from_data_frame(df_1, directed = FALSE)
E(graph2)$weight <- df_1$edge_weight
plot(graph1)

edge_strengts <- strength(graph1)

The output I am getting from strength function is the sum of edge weight from each vertex of the graph.

 ID_1    ID_2    ID_3    ID_4    ID_5   ID_16 Node_30   ID_11  Node_3 
   0.50    0.90    2.20    1.50    1.20    0.09    0.70    0.59    0.70

Now, I have an edge list and I want to get the sum of the edge weight only for those lists (instead of getting the sum of edges for one vertex). For more clarification, say I have the given edge list,

         nodeA      nodeB 
1        ID_2       ID_4  
2        ID_2       ID_5 
3        ID_1       ID_16 

I want to get the sum of the edges only for the above-listed edge from the given graph (note that the graph is undirected). The output should something like this

         nodeA      nodeB    some_of_weight
1        ID_2       ID_4     1.70
2        ID_2       ID_5     1.40
3        ID_1       ID_16    0.59

For the first edge (ID_2 to ID_4) the sum is 1.70 (e.g: ID_2 to ID_3 = 0.9, and ID_3 to ID_4 = 0.8, so, 0.9 + 0.8 = 1.70) and so on for all edge list.

Can you tell me, how can I do this job?

Multiple paths for an edge

The graph can contain multiple paths for edges (i.e., for an edge we can have 1 or more than one different path). Say, we can go ID_3 to ID_4 in 2 ways (i) ID_3 -- ID_2 -- ID_4 (total path weight is 2.4) and (ii) ID_3 -- ID_5 -- ID_4 (total path weight is 1.5). In this case, I want to take the maximum path weight.

Reproducible data for the multiple paths

nodeA <- c("ID_1", "ID_2",  "ID_4", "ID_5", "ID_16", "Node_30", "ID_6", "ID_2")
nodeB <- c("ID_11", "ID_3",  "ID_5", "ID_3", "ID_11", "Node_3", "ID_3", "ID_4")
edge_weight <- c(0.5, 0.9, 0.8, 0.7, 0.5, 0.09, 0.7, 1.5)
2 Answers

Update

Since you are looking for longest path between two vertices, you can try the code below

df_2$max_sum_weight <- apply(
  df_2,
  1,
  function(x) {
    max(sapply(
      all_simple_paths(graph1, x[["v"]], x[["to"]]),
      function(v) {
        sum(E(graph1)$weight[get.edge.ids(graph1, c(rbind(head(v, -1), v[-1])))])
      }
    ))
  }
)

which gives

> df_2
     v    to max_sum_weight
1 ID_2  ID_4            2.4
2 ID_2  ID_5            2.3
3 ID_1 ID_16            1.0
4 ID_3  ID_4            2.4

Data

df_2 <- data.frame(
  v = c("ID_2", "ID_2", "ID_1", "ID_3"),
  to = c("ID_4", "ID_5", "ID_16", "ID_4")
)

Previous Answer (shortest paths)


Try shortest.paths

transform(
  df_2,
  sum_of_weight = diag(shortest.paths(graph1, v, to))
)

or

transform(
  df_2,
  sum_of_weight = shortest.paths(graph1)[as.matrix(df_2)]
)

which gives

     v    to sum_of_weight
1 ID_2  ID_4          1.70
2 ID_2  ID_5          1.40
3 ID_1 ID_16          0.59

I would use the following approach:

Load packages

library(igraph)
#> 
#> Attaching package: 'igraph'
#> The following objects are masked from 'package:stats':
#> 
#>     decompose, spectrum
#> The following object is masked from 'package:base':
#> 
#>     union

Load data

nodeA <- c("ID_1", "ID_2", "ID_3", "ID_4", "ID_5", "ID_16", "Node_30")
nodeB <- c("ID_11", "ID_3", "ID_4", "ID_5", "ID_3", "ID_11", "Node_3")
df <- data.frame(nodeA, nodeB)
graph <- graph_from_data_frame(df, directed = FALSE)
E(graph)$weight <- c(0.5, 0.9, 0.8, 0.7, 0.5, 0.09, 0.7)

Estimate all pairwise distances between those nodes

all_distances <- distances(
  graph = graph, 
  v = c("ID_2", "ID_2", "ID_1"), 
  to = c("ID_4", "ID_5", "ID_16")
)

Check output

all_distances
#>      ID_4 ID_5 ID_16
#> ID_2  1.7  1.4   Inf
#> ID_2  1.7  1.4   Inf
#> ID_1  Inf  Inf  0.59

Take the diagonal

diag(all_distances)
#> [1] 1.70 1.40 0.59

Please notice that duplicated vertices in the to argument are discarded. For example:

distances(graph, v = c("ID_2", "ID_5", "ID_4"), c("ID_3", "ID_3", "ID_5"))
#> Error in distances(graph, v = c("ID_2", "ID_5", "ID_4"), c("ID_3", "ID_3", : At structural_properties.c:4461 : Duplicate vertices in `to', this is not allowed, Invalid value

In that case, you should compute the “unique” vertices and then take the relevant matches:

idx_from <- c("ID_2", "ID_5", "ID_4")
idx_to <- c("ID_3", "ID_3", "ID_5") # note the duplicated names
idx_to_unique <- unique(idx_to)
all_distances <- distances(graph, idx_from, idx_to_unique)
diag(all_distances[, match(idx_to, idx_to_unique)])
#> [1] 0.9 0.5 0.7

Created on 2021-11-06 by the reprex package (v2.0.1)

EDIT: Add example of summing along longest path

# packages
suppressPackageStartupMessages(library(igraph))

# data
nodeA <- c("ID_1", "ID_2",  "ID_4", "ID_5", "ID_16", "Node_30", "ID_6", "ID_2")
nodeB <- c("ID_11", "ID_3",  "ID_5", "ID_3", "ID_11", "Node_3", "ID_3", "ID_4")
df <- data.frame(nodeA, nodeB)
graph <- graph_from_data_frame(df, directed = FALSE)
E(graph)$weight <- c(0.5, 0.9, 0.8, 0.7, 0.5, 0.09, 0.7, 1.5)

# Sum weights along longest path
my_sum_weights <- function(graph, from, to) {
  # Compute all simple paths
  my_all_simple_paths <- all_simple_paths(
    graph = graph, 
    from = from, 
    to = to
  )
  
  # Check if there is at least a path
  if (length(my_all_simple_paths) == 0L) {
    return(Inf)
  }
  
  # In that case, sum weights along each path
  all_sum_weights <- numeric(length(my_all_simple_paths))
  for (i in seq_along(my_all_simple_paths)) {
    edges_weights <- E(graph, path = my_all_simple_paths[[i]])$weight
    all_sum_weights[[i]] <- sum(edges_weights)
  }
  
  max(all_sum_weights)
}

# Examples
my_sum_weights(graph, "ID_3", "ID_4")
#> [1] 2.4
my_sum_weights(graph, "ID_6", "ID_4")
#> [1] 3.1
my_sum_weights(graph, "ID_5", "ID_2")
#> [1] 2.3
mapply(my_sum_weights, from = c("ID_3", "ID_6", "ID_1"), MoreArgs = list(to = "ID_4", graph = graph))
#> ID_3 ID_6 ID_1 
#>  2.4  3.1  Inf

Created on 2021-11-06 by the reprex package (v2.0.1)

Please notice that there are exponentially many paths between two vertices of a graph, and you may run out of memory when using all_simple_paths function.

Related