igraph bipartite network projection ignores direction

Question

Example:

require(igraph)
require(tidygraph)
require(ggraph)
require(data.table)

nodes <- data.table(id = 1:6, 
                    label = c("a1", "b1", "a2", "a3", "b2", "a4"), 
                    type = c("A", "B", "A", "A", "B", "A"))

edges <- data.table(from = c(1, 2, 2, 3, 5),
                    to = c(2, 3, 4, 5, 6))

network <- graph_from_data_frame(d = edges, vertices = nodes, directed = TRUE)

ggraph(network) + 
  geom_edge_link(arrow = arrow(length = unit(4, 'mm')), 
                 start_cap = circle(3, 'mm'), 
                 end_cap = circle(3, 'mm')) + 
  geom_node_point(aes(color = type), size = 7) +
  geom_node_text(aes(label = label)) +
  theme_graph()

This is what we get:

Then we create projections:

V(network)$type <- bipartite_mapping(network)$type
network_projections <- bipartite_projection(network)

ggraph(network_projections$proj1) + 
  geom_edge_link(arrow = arrow(length = unit(4, 'mm')), 
                 start_cap = circle(3, 'mm'), 
                 end_cap = circle(3, 'mm')) + 
  geom_node_point(size = 7, color = 2, alpha = .6) +
  geom_node_text(aes(label = label)) +
  theme_graph()

And this is what we get:

Projection shows link a2 -> a3, which should not be there. Which clearly means that directionality was not taken into the account.

As much as I found out - underlying incidence matrix computed by igraph library is computed in a way that does not consider directionality. Is there some function that I missed or other R libraries out there that allow for directional projections of bipartite networks?

statespace statespace · Accepted Answer · 2018-11-27T12:49:27

This is by no means an optimal solution, more like workaround:

(continue from the code in original question)

# get a list of adjacent vertices from perspective of projections to validate directional connection
adj_vert <- adjacent_vertices(network_projections$proj1, v = nodes[type == "A", .I])

# container
projection_edges <- data.table(from = character(),
                               to = character())

for(i in names(adj_vert)){

  # find simplest path, from iterated vertice to vector of shortlisted names
  orig_paths <- all_simple_paths(network, from = as.numeric(i), to = as.numeric(names(adj_vert[[i]])), mode = "out")

  if(length(orig_paths) > 0){
    for(j in 1:length(orig_paths)){

      # for each path, take first and last element to skip "B" nodes in between
      projection_edges <- rbind(projection_edges,
                                data.table(from = names(orig_paths[[j]])[1],
                                           to = rev(names(orig_paths[[j]]))[1]))
    }
  }
}

# corrected projection

network_projection_corrected <- graph_from_data_frame(d = projection_edges, vertices = nodes[type == "A"], directed = TRUE)

ggraph(network_projection_corrected) + 
  geom_edge_link(arrow = arrow(length = unit(4, 'mm')), 
                 start_cap = circle(3, 'mm'), 
                 end_cap = circle(3, 'mm')) + 
  geom_node_point(aes(color = type), size = 7) +
  geom_node_text(aes(label = label)) +
  theme_graph()

We get this:

This doesn't look VERY terrible, even if it's a nested loop. Because for every loop all adjacent "A"-type vertices are known, and we just effectively check directional connection. Yet, I think this should be a built-in functionality.

Also, I am not aware of possible errors my proposed approach will bring for 'real-life' networks. So it's by no means solid.

igraph bipartite network projection ignores direction

1 Answers